网络流/最大流

　　愚人节快乐XD

　　这题是给一个混合图（既有有向边又有无向边），让你判断是否有欧拉回路……

　　我们知道如果一个【连通】图中每个节点都满足【入度=出度】那么就一定有欧拉回路……

　　那么每条边都可以贡献一个出度出来，对于一条边u->v：

　　　　连S->edge cap=1;

　　　　如果是有向边，就连 edge->v cap=1;

　　　　否则（无向边）连edge->u cap=1, edge->v cap=1;

　　然后每个点的总度数我们是知道的……那么它最后的【出度】就等于总度数/2。（这个地方我傻逼了没想到……

　　P.S.这题是跟POJ2699比较类似的

 Source Code

 Problem:         User: sdfzyhy

 Memory: 1148K        Time: 32MS

 Language: G++        Result: Accepted

     Source Code

     //BZOJ 1000

     #include<vector>

     #include<cstdio>

     #include<cstdlib>

     #include<cstring>

     #include<iostream>

     #include<algorithm>

     #define rep(i,n) for(int i=0;i<n;++i)

     #define F(i,j,n) for(int i=j;i<=n;++i)

     #define D(i,j,n) for(int i=j;i>=n;--i)

     using namespace std;

     int getint(){

         int v=,sign=; char ch=getchar();

         while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

         while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

         return v*sign;

     }

     typedef long long LL;

     const int N=,M=,INF=~0u>>;

     /*******************tamplate********************/

     int n,m,ans,du[];

     struct edge{int to,v;};

     struct Net{

         edge E[M];

         int next[M],head[N],cnt;

         void ins(int x,int y,int z){E[++cnt]=(edge){y,z};next[cnt]=head[x];head[x]=cnt;}

         void add(int x,int y,int z){ins(x,y,z); ins(y,x,);}

         int S,T,d[N],Q[M],cur[N];

         bool mklevel(){

             F(i,,T) d[i]=-;

             int l=,r=-;

             Q[++r]=S; d[S]=;

             while(l<=r){

                 int x=Q[l++];

                 for(int i=head[x];i;i=next[i])

                     if(E[i].v && d[E[i].to]==-){

                         d[E[i].to]=d[x]+;

                         Q[++r]=E[i].to;

                     }

             }

             return d[T]!=-;

         }

         int dfs(int x,int a){

             if(x==T)return a;

             int flow=;

             for(int &i=cur[x];i && flow<a;i=next[i])

                 if(E[i].v && d[E[i].to]==d[x]+){

                     int f=dfs(E[i].to,min(a-flow,E[i].v));

                     E[i].v-=f;

                     E[i^].v+=f;

                     flow+=f;

                 }

             if(!flow) d[x]=-;

             return flow;

         }

         void Dinic(){

             while(mklevel()){

                 F(i,S,T) cur[i]=head[i];

                 ans+=dfs(S,INF);

             }

         }

         void init(){

             n=getint(); m=getint();

             cnt=; memset(head,,sizeof head);

             F(i,,n) du[i]=;

             S=; T=n+m+; ans=;

             int x,y,z;

             F(i,,m){

                 x=getint(); y=getint(); z=getint();

                 add(S,i,); add(i,y+m,);

                 if (!z) add(i,x+m,);

                 du[x]++; du[y]++;

             }

             F(i,,n){

                 if (du[i]%){puts("impossible");return;}

                 add(i+m,T,du[i]/);

             }

             Dinic();

             if (ans==m) puts("possible");

             else puts("impossible");

         }

     }G1;

     int main(){

     #ifndef ONLINE_JUDGE

         freopen("input.txt","r",stdin);

     //    freopen("output.txt","w",stdout);

     #endif

         int T=getint();

         while(T--) G1.init();

         return ;

     }

向边

【POJ】【1637】Sightseeing tour

网络流/最大流