poj 1637 Sightseeing tour——最大流+欧拉回路

先给无向边随便定向，如果一个点的入度大于出度，就从源点向它连 ( 入度 - 出度 / 2 ) 容量的边，意为需要流出去这么多；流出去1表示改了一条边的方向，会使自己出度-1、入度+1，所以容量要/2；出度大于入度的点类似地连向汇点；无向边按给它定的方向的反方向连上容量为1的边；最后看看能否满流即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,M=,INF=N*M;

int n,m,deg[N],hd[N],xnt,cur[N],sm[N],gn[N],gt[N],dfn[N];

struct Ed{

  int to,nxt,cap;

  Ed(int a=,int b=,int c=):to(a),nxt(b),cap(c) {}

}ed[M+N<<];

queue<int> q;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

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

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void init()

{

  xnt=;memset(deg,,sizeof deg);//xnt=1!!!

  memset(sm,,sizeof sm);memset(hd,,sizeof hd);

  memset(gn,,sizeof gn);memset(gt,,sizeof gt);

}

void add(int x,int y,int z)

{

  ed[++xnt]=Ed(y,hd[x],z);hd[x]=xnt;

  ed[++xnt]=Ed(x,hd[y],);hd[y]=xnt;

}

bool bfs()

{

  memset(dfn,,sizeof dfn);

  dfn[]=;q.push();

  while(q.size())

    {

      int k=q.front();q.pop();

      for(int i=hd[k],v;i;i=ed[i].nxt)

    if(!dfn[v=ed[i].to]&&ed[i].cap)

      dfn[v]=dfn[k]+,q.push(v);

    }

  return dfn[n+];

}

int dinic(int cr,int flow)

{

  if(cr==n+)return flow;//

  int use=;

  for(int& i=cur[cr],v;i;i=ed[i].nxt)

    if(dfn[v=ed[i].to]==dfn[cr]+&&ed[i].cap)

      {

    int tmp=dinic(v,min(flow-use,ed[i].cap));

    if(!tmp)dfn[v]=n+;

    use+=tmp;ed[i].cap-=tmp;ed[i^].cap+=tmp;

    if(use==flow)return use;

      }

  return use;

}

int main()

{

  int T=rdn();

  while(T--)

    {

      n=rdn();m=rdn();init();

      for(int i=,u,v,fx;i<=m;i++)

    {

      u=rdn();v=rdn();fx=rdn();

      deg[u]++;deg[v]++;sm[v]++;sm[u]--;//in - out

      if(!fx)add(v,u,);

      else gn[v]++,gt[u]++;

    }

      bool flag=;int val=;

      for(int i=;i<=n;i++)

    {

      if((deg[i]&)||gn[i]>(deg[i]>>)||gt[i]>(deg[i]>>))

        {flag=;break;}

      if(sm[i]>)add(,i,sm[i]>>),val+=sm[i]>>;

      else if(sm[i]<)add(i,n+,-sm[i]>>);

    }

      if(flag){puts("impossible");continue;}

      int mxflow=;

      while(bfs())

    {memcpy(cur,hd,sizeof hd);mxflow+=dinic(,INF);}//fr:0 !!!

      if(mxflow==val)puts("possible");

      else puts("impossible");

    }

  return ;

}

秒客网

poj 1637 Sightseeing tour——最大流+欧拉回路

相关文章