高级网络流建图啊！
起初看这题，直接吓尿了... 不会....
思路看这里......
很不错的分析啦。
一点点二逼的错误，让我找了好久！很久没这么二了！一个大于号打反了.. 还有一个变量没有初始化，我去！样例都让我跑对了！
CODE：
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#define MN 222
#define ME 1111
#define FF(i,a,b) for( int i=a;i<b;i++ )
#define CC(a) memset( a,0,sizeof(a) )
template<class T>void inline checkmin( T &a,T b ){ if(a==-1||a>b) a=b; }
using namespace std;struct edge{int u,v,p;
}E[ME];
bool Impos;
int NV,NE,s,t,in[MN],out[MN],tot;
int maze[MN][MN],gap[MN],dis[MN],pre[MN],cur[MN];
void setG()
{CC(maze);CC(in);CC(out);scanf( "%d%d",&NV,&NE );s=0;t=NV+1;Impos=false;tot=0;FF( i,0,NE ){scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].p );out[E[i].u]++;in[E[i].v]++;}FF( i,1,t ){if( abs(in[i]-out[i])&1 )Impos=true;if( in[i]>out[i] )maze[i][t]=(in[i]-out[i])/2;elsemaze[s][i]=(out[i]-in[i])/2;}FF( i,1,t )tot+=maze[s][i];FF( i,0,NE )if( E[i].p==0 )maze[E[i].u][E[i].v]++;
}int sap()
{CC(cur),CC(pre),CC(gap),CC(dis);int u=pre[s]=s,maxflow=0,aug=-1;gap[0]=t+1;while( dis[s]<=t ){
loop: for( int v=cur[u];v<=t;v++ )if( maze[u][v]&&dis[u]==dis[v]+1 ){cur[u]=v;pre[v]=u;checkmin( aug,maze[u][v] );u=v;if( v==t ){ maxflow+=aug;for( u=pre[u];v!=s;v=u,u=pre[u] ){ maze[u][v]-=aug;maze[v][u]+=aug;} aug=-1;}goto loop;}int mind=t;for( int v=0;v<=t;v++ )if( maze[u][v]&&mind>dis[v] ){cur[u]=v;mind=dis[v];}if( --gap[dis[u]]==0 )break;gap[dis[u]=mind+1]++;u=pre[u];}return maxflow;
}int main()
{int T;scanf( "%d",&T );while( T-- ){setG();//printf( "tot:%d\n",tot );if( Impos || tot!=sap() )printf( "impossible\n" );elseprintf( "possible\n" );}return 0;
}