SRM 410 DIV1 Easy - AddElectricalWires (復習××)

February 22, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182

ノードが複数存在し、任意のノード同士がつながっている。
また、任意のノードが電力源につながっている。ただし、複数の電力源につながってはいけない。

このとき、接続可能なエッジの数を求める。

解き方

各電力源につながっているノードの集合ごとに、残りでつなぐことのできるエッジ数を求める。
また、そのうち最大の集合と、電力源につながっていないノードの積も答えに加わる。

あるノードの集合におけるエッジ数は、残りのエッジ数ではなく最大エッジ数を求めた後で、最後に最初に存在するエッジ数を引いてあげればコーディングが簡単になる。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int cnt,p[50],n;
vector<string> W;

class AddElectricalWires {

public:

void dfs(int x){
if(p[x])return;
p[x]=1;
cnt++;
FORE(i,0,n)if(W[x][i]=='1'&&p[i]==0)dfs(i);
}

int maxNewWires(vector<string> wires, vector<int> grid) {
n=wires.size();
W=wires;
int ret=0;
int left=n;
memset(p,0,sizeof(p));

int curedge=0;
FORE(i,0,wires.size())FORE(j,0,wires[0].size())if(wires[i][j]=='1')curedge++;
curedge/=2;

int maxgrid=0;
FORE(i,0,grid.size()){
cnt=0;
dfs(grid[i]);
ret+=cnt*(cnt-1)/2;
left-=cnt;
maxgrid=max(maxgrid,cnt);
}
ret+=left*(left-1)/2+left*maxgrid;

return ret-curedge;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int used[51],n;
vector<string> w;

class AddElectricalWires {

public:

int dfs(int x){
int ret=1;
used[x]=1;
FORE(i,0,n)if(w[x][i]=='1'&&used[i]==0)ret+=dfs(i);
return ret;
}

int maxNewWires(vector<string> wires, vector<int> grid) {
n=wires.size();
w=wires;
memset(used,0,sizeof(used));

int ret=0,ma=0,left=n;
FORE(i,0,grid.size())if(used[grid[i]]==0){
int cnt=dfs(grid[i]);
ret+=cnt*(cnt-1)/2;
ma=max(ma,cnt);
left-=cnt;
}

ret-=ma*(ma-1)/2;
ret+=(ma+left)*(ma+left-1)/2;
FORE(i,0,n)FORE(j,i,n)if(wires[i][j]=='1')ret--;
return ret;
}

};

グラフ