题目：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=205,xm=3005,inf=0x3f3f3f3f; int n,m,hd[xn],ct=1,to[xm],nxt[xm],dis[xn],cur[xn],c[xm],ind[xn],cd[xn]; queue<int>q; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',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>0?x:-x;} bool bfs() { while(q.size())q.pop(); memset(dis,0,sizeof dis); dis[0]=1; q.push(0); 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]+1,q.push(u); } return dis[n+1]; } int dfs(int x,int fl) { if(x==n+1)return fl; int ret=0; for(int &i=cur[x],u;i;i=nxt[i]) { if(dis[u=to[i]]!=dis[x]+1||!c[i])continue; int tmp=dfs(u,min(fl-ret,c[i])); if(!tmp)dis[u]=0; c[i]-=tmp; c[i^1]+=tmp; ret+=tmp; if(ret==fl)break; } return ret; } int main() { int T=rd(); while(T--) { ct=1; memset(hd,0,sizeof hd); memset(ind,0,sizeof ind); memset(cd,0,sizeof cd); n=rd(); m=rd(); for(int i=1,x,y,z;i<=m;i++) { x=rd(); y=rd(); z=rd(); cd[x]++; ind[y]++; if(!z)add(y,x,1),add(x,y,0); } bool fl=0; int goal=0; for(int i=1;i<=n;i++) { if(abss(ind[i]-cd[i])%2){fl=1; break;} if(ind[i]>cd[i])add(0,i,(ind[i]-cd[i])/2),add(i,0,0),goal+=(ind[i]-cd[i])/2; else if(ind[i]<cd[i])add(i,n+1,(cd[i]-ind[i])/2),add(n+1,i,0); } if(fl){puts("impossible"); continue;} int ans=0; while(bfs()) { memcpy(cur,hd,sizeof hd); ans+=dfs(0,inf); } if(ans==goal)puts("possible"); else puts("impossible"); } return 0; }