poj 1637 Sightseeing tour 网络流

经典题目，很多书上都有解答。

首先得用一个结论，一个联通的有向图存在欧拉回路当且仅当每个点的入度等于出度。

那么这个题目的做法就是先给无向边任意定向，如果某个点的入度出度之差为奇数，那么肯定无解。

否则源点向入度大于出度的点连边，出度大于入度的向汇点连边，网络流判断能不能使得最后每个点的入度都等于出度。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=2e2+9,inf=1e9;int n,m;int in[maxn],out[maxn];int head[maxn],lon;int que[maxn],level[maxn];struct{    int next,to,c;}e[maxn*maxn];void edgeini(){    memset(head,-1,sizeof(head));    lon=-1;}void edgemake(int from,int to,int c){    e[++lon].c=c;    e[lon].to=to;    e[lon].next=head[from];    head[from]=lon;}bool makelevel(int s,int t){    memset(level,0,sizeof(level));    int front=1,end=0;    que[++end]=s;    level[s]=1;    while(front<=end)    {        int u=que[front++];        if(u==t) return true;        for(int k=head[u];k!=-1;k=e[k].next)        {            int v=e[k].to;            if(!level[v]&&e[k].c)            {                que[++end]=v;                level[v]=level[u]+1;            }        }    }    return false;}int dfs(int now,int t,int maxf){    int ret=0;    if(t==now) return maxf;    for(int k=head[now];k!=-1;k=e[k].next)    {        int u=e[k].to;        if(e[k].c&&level[u]==level[now]+1)        {            int f=dfs(u,t,min(maxf-ret,e[k].c));            e[k].c-=f;            e[k^1].c+=f;            ret+=f;            if(ret==maxf) return ret;        }    }    return ret;}int maxflow(int s,int t){    int ret=0;    while(makelevel(s,t))    ret+=dfs(s,t,inf);    return ret;}void makegraph(){    for(int i=1;i<=n;i++)    if(in[i]>out[i])    {        int tmp=in[i]-out[i]>>1;        edgemake(0,i,tmp);        edgemake(i,0,0);    }    else    {        int tmp=out[i]-in[i]>>1;        edgemake(i,n+1,tmp);        edgemake(n+1,i,0);    }}void init(){    edgeini();    memset(in,0,sizeof(in));    memset(out,0,sizeof(out));}int main(){//    freopen("in.txt","r",stdin);    int T;    scanf("%d",&T);    while(T--)    {        init();        scanf("%d%d",&n,&m);        for(int i=1,from,to,tmp;i<=m;i++)        {            scanf("%d%d%d",&from,&to,&tmp);            in[to]++;            out[from]++;            if(tmp==0)            {                edgemake(to,from,1);                edgemake(from,to,0);            }        }        bool flag=false;        for(int i=1;i<=n;i++)        if((in[i]-out[i])%2) flag=true;        if(flag)        {            printf("impossible\n");            continue;        }        makegraph();        int ans=maxflow(0,n+1)*2;        int sum1=0,sum2=0;        for(int i=1;i<=n;i++)        if(in[i]>out[i]) sum1+=in[i]-out[i];        else sum2+=out[i]-in[i];        if(sum1==sum2&&sum1==ans) printf("possible\n");        else printf("impossible\n");    }    return 0;}