SRM 648 DIV2 Middle - Fragile2 (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13648&rd=16312
・このうち２つの頂点を選び、グラフから消した時に木の集合が増える
頂点の選び方を全て求める。
解き方
・頂点数は２０なので、頂点の選び方は２０C2となり全探索で解ける。
・２つの頂点を選んだときにできる木の集合の数を求め、頂点を消さないときよりも
集合の数が増えるかどうか判定すればよい。
コード
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[30],n;
vector<string> g;
class Fragile2 {
public:
void dfs(int x){
used[x]=1;
FORE(i,0,n)if(!used[i] && g[x][i]=='Y')dfs(i);
}
int countPairs(vector<string> graph) {
n=graph.size();
g=graph;
memset(used,0,sizeof(used));
int sum=0;
FORE(i,0,n)if(!used[i]){
sum++;
dfs(i);
}
int ret=0;
FORE(i,0,n)FORE(j,i+1,n){
memset(used,0,sizeof(used));
used[i]=1,used[j]=1;
g=graph;
FORE(k,0,n)g[i][k]=g[k][i]=g[j][k]=g[k][j]='N';
int tmp=0;
FORE(k,0,n)if(!used[k]){
tmp++;
dfs(k);
}
if(tmp>sum)ret++;
}
return ret;
}
};
#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[30],n;
vector<string> g;
class Fragile2 {
public:
void dfs(int x){
used[x]=1;
FORE(i,0,n)if(!used[i] && g[x][i]=='Y')dfs(i);
}
int countPairs(vector<string> graph) {
n=graph.size();
g=graph;
memset(used,0,sizeof(used));
int sum=0;
FORE(i,0,n)if(!used[i]){
sum++;
dfs(i);
}
int ret=0;
FORE(i,0,n)FORE(j,i+1,n){
memset(used,0,sizeof(used));
used[i]=1,used[j]=1;
g=graph;
FORE(k,0,n)g[i][k]=g[k][i]=g[j][k]=g[k][j]='N';
int tmp=0;
FORE(k,0,n)if(!used[k]){
tmp++;
dfs(k);
}
if(tmp>sum)ret++;
}
return ret;
}
};
