判断是否满流以及添加的边是否为整数


#include <cstdio>  
#include <algorithm>
#include <cstring>
#include <iostream>  
using namespace std;  
const int oo=1e9;  
/**oo 表示无穷大*/  
const int mm=111111;  
/**mm 表示边的最大数量，记住要是原图的两倍，在加边的时候都是双向的*/  
const int mn=999;  
/**mn 表示点的最大数量*/  
int node,src,dest,edge;  
/**node 表示节点数，src 表示源点，dest 表示汇点，edge 统计边数*/  
int ver[mm],flow[mm],next[mm];  
/**ver 边指向的节点，flow 边的容量，next 链表的下一条边*/  
int head[mn],work[mn],dis[mn],q[mn];  
/**head 节点的链表头，work 用于算法中的临时链表头，dis 计算距离*/  
  
/**初始化链表及图的信息*/  
void prepare(int _node,int _src,int _dest)  
{  
    node=_node,src=_src,dest=_dest;  
    for(int i=0; i<node; ++i)head[i]=-1;  
    edge=0;  
}  
/**增加一条u 到v 容量为c 的边*/  
void addedge(int u,int v,int c)  
{  
    ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;  
    ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;  
}  
/**广搜计算出每个点与源点的最短距离，如果不能到达汇点说明算法结束*/  
bool Dinic_bfs()  
{  
    int i,u,v,l,r=0;  
    for(i=0; i<node; ++i)dis[i]=-1;  
    dis[q[r++]=src]=0;  
    for(l=0; l<r; ++l)  
        for(i=head[u=q[l]]; i>=0; i=next[i])  
            if(flow[i]&&dis[v=ver[i]]<0)  
            {  
                /**这条边必须有剩余容量*/  
                dis[q[r++]=v]=dis[u]+1;  
                if(v==dest)return 1;  
            }  
    return 0;  
}  
/**寻找可行流的增广路算法，按节点的距离来找，加快速度*/  
int Dinic_dfs(int u,int exp)  
{  
    if(u==dest)return exp;  
    /**work 是临时链表头，这里用i 引用它，这样寻找过的边不再寻找*/  
    for(int &i=work[u],v,tmp; i>=0; i=next[i])  
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)  
        {  
            flow[i]-=tmp;  
            flow[i^1]+=tmp;  
            /**正反向边容量改变*/  
            return tmp;  
        }  
    return 0;  
}  
int Dinic_flow()  
{  
    int i,ret=0,delta;  
    while(Dinic_bfs())  
    {  
        for(i=0; i<node; ++i)work[i]=head[i];  
        while(delta=Dinic_dfs(src,oo))ret+=delta;  
    }  
    return ret;  
}  
int G[mn][mn];
int indeg[mn],outdeg[mn];
int main()
{
	 int T,m,s;
	 scanf("%d",&T);
	 while(T--)
	 {
	 	memset(indeg,0,sizeof(indeg));
	 	memset(outdeg,0,sizeof(outdeg));
	 	memset(G,0,sizeof(G));
	 	scanf("%d%d",&m,&s);
	 	prepare(m+2,0,m+1);
	 	for(int i = 0;i < s;i++)
	 	{
	 		int u,v,state;
	 		scanf("%d%d%d",&u,&v,&state);
	 		if(u == v) continue;
	 		if(state == 0) G[u][v] ++;
	 		indeg[v]++;
	 		outdeg[u]++;
		 }
		 for(int i = 1;i <= m;i++)
		 {
		 	for(int j = 1;j <= m;j++)
		 	{
		 		if(G[i][j]) addedge(i,j,G[i][j]);
			 }
		 }
		 int exp = 0;
		 for(int i = 1;i <= m;i++)
		 {
		 	if(indeg[i] == outdeg[i]) continue;
		 	else if(indeg[i] > outdeg[i])
		 	{
		 		addedge(i,m+1,(indeg[i]-outdeg[i])/2 );
		 		exp += (indeg[i]-outdeg[i])/2;
		 		if((indeg[i]-outdeg[i])/2==0) 
		 		{
		 			goto s;
				 }
			}
			else
			{
				addedge(0,i,(outdeg[i] - indeg[i])/2);
				if((indeg[i]-outdeg[i])/2 ==0 ) 
		 		{
		 			goto s;
				 }
			}
		 }
		 if(exp == Dinic_flow())
		 {
		 	puts("possible");
		 }
		 else
		 {
		 	s:puts("impossible");
		 }
		 
	 }
}