题目:http://poj.org/problem?id=1637
建图很妙;
先给无向边随便定向,这样会有一些点的入度不等于出度;
如果入度和出度的差值不是偶数,也就是说这个点的总度数是奇数,那么一定无解;
随便定向后,如果定向 x -> y,那么从 y 向 x 连一条容量为1的边,将来选了这条边,表示重新定向成 y -> x 了;
考虑如果选了这条边,那么 x 的出度-1,入度+1,变化量是2;
所以对于每个点,如果入度>出度,从源点向它连容量为 (入度-出度)/2 的边,因为刚才改向变化量为2,但容量是1,所以这里容量要 /2;
这样,为了流量守恒,这个点会流出去 (入度-出度)/2 的流量,对应原图,就是通过改向使这个点的入度=出度;
同理,如果入度<出度,从它向汇点连容量为 (出度-入度)/2 的边;
然后看是否满流即可。
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=,xm=,inf=0x3f3f3f3f;
int n,m,hd[xn],ct=,to[xm],nxt[xm],dis[xn],cur[xn],c[xm],ind[xn],cd[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}
int abss(int x){return x>?x:-x;}
bool bfs()
{
while(q.size())q.pop();
memset(dis,,sizeof dis);
dis[]=; q.push();
while(q.size())
{
int x=q.front(); q.pop();
for(int i=hd[x],u;i;i=nxt[i])
if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);
}
return dis[n+];
}
int dfs(int x,int fl)
{
if(x==n+)return fl;
int ret=;
for(int &i=cur[x],u;i;i=nxt[i])
{
if(dis[u=to[i]]!=dis[x]+||!c[i])continue;
int tmp=dfs(u,min(fl-ret,c[i]));
if(!tmp)dis[u]=;
c[i]-=tmp; c[i^]+=tmp;
ret+=tmp; if(ret==fl)break;
}
return ret;
}
int main()
{
int T=rd();
while(T--)
{
ct=; memset(hd,,sizeof hd);
memset(ind,,sizeof ind); memset(cd,,sizeof cd);
n=rd(); m=rd();
for(int i=,x,y,z;i<=m;i++)
{
x=rd(); y=rd(); z=rd();
cd[x]++; ind[y]++;
if(!z)add(y,x,),add(x,y,);
}
bool fl=; int goal=;
for(int i=;i<=n;i++)
{
if(abss(ind[i]-cd[i])%){fl=; break;}
if(ind[i]>cd[i])add(,i,(ind[i]-cd[i])/),add(i,,),goal+=(ind[i]-cd[i])/;
else if(ind[i]<cd[i])add(i,n+,(cd[i]-ind[i])/),add(n+,i,);
}
if(fl){puts("impossible"); continue;}
int ans=;
while(bfs())
{
memcpy(cur,hd,sizeof hd);
ans+=dfs(,inf);
}
if(ans==goal)puts("possible");
else puts("impossible");
}
return ;
}