Posted on 2010-10-14 20:07
成幸毅 阅读(466)
评论(0) 编辑 收藏 引用
给出一个N个点和M条边的混合图，求出它的一条欧拉回路，如果没有，输出无解信息。
无向边只能经过一次，所以不能把它拆成两条方向相反的有向边，而只能给每条无向边定向。有向图欧拉回路的有条性质是：当且仅当，图连通，并且每个节点的入度等于出度！！这题可以先给每条无向边定向，随意定。这样，每个节点现在大有可能出度不等于入度。如果一个点入度大于出度，那么让这s与这点相连，边容量为(出度-入度)/2;代表这个节点经过两次修改后能让出度等于入度。反之，连t节点。道理一样。如果是满流，那就对了，欧拉图。
int main() 
{
int cas;
scanf("%d",&cas);
while(cas--) {
memset(degree,0,sizeof(degree));
memset(head,-1,sizeof(head));
sps = 0;
int sum = 0;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d",&vex1[i],&vex2[i],&dir[i]);
degree[vex1[i]]++;
degree[vex2[i]]--;
}
int i;
for( i = 1; i <= n; i++) {
if(abs(degree[i])&1)
break;
}
if(i <= n) {
printf("impossible\n"); continue;
}
s = 0,t = n+1;
NN = t+1;
for(int i = 0; i < m; i++) {
if(!dir[i] && vex1[i] != vex2[i])
addedge(vex1[i],vex2[i],1);
}
for(int i = 1; i <= n;i++) {
if(degree[i] > 0) {
addedge(s,i,(degree[i])/2);
sum += degree[i]/2;
}
else if(degree[i] < 0) {
addedge(i,t,-degree[i]/2);
}
}
if(maxFlow(s,t) == sum) {
printf("possible\n");
}
else
printf("impossible\n");
}
// system("pause");
return 0;
}
