首页 > 代码库 > POJ1637_Sightseeing tour

POJ1637_Sightseeing tour

2024-07-12 21:39:26   224人阅读

给一个联通图，有的是单向边，有的是双向边，问是否存在欧拉回路。

乍一看毫无思路，可以这样来搞，对于每条无向边，我们随便指定一个方向，看看是否能够做到所有点的度数之和为偶数。

接下来，对于我们指定的边，假设指定的是U->V,那么我们也同时在网络中设置一条同样的边，使得流量为1，最后如果某点的出入度只差不为0，那么我们把那个差除以2，这表示我们在这个点处至少需要改变多少条无向边的方向。对于出大于入的点，我们连源点，对于如大于出的点，我们连汇点，最后跑最大流看看时候所有的与源点和汇点的边能否满流即可。

一开始的想法是，不指定方向，直接跑最大流，这样是错的，因为无法保证每条无向边最终都被指定了方向，也就是对应回题目里面，不一定无向边都遍历到了，而通过首先指定一个方向，然后再改变方向的方法可以保证这一点。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 2220#define maxm 22220using namespace std;int to[maxm],next[maxm],first[maxn],c[maxm],edge;int d[maxn],tag[maxn],can[maxn],dgr[maxn],TAG=520;int n,m,T,s,t,sum,ans;int Q[maxn],bot,top;const int inf=~0U>>1;void _init(){    sum=ans=s=0,t=n+1,edge=-1;    for (int i=s; i<=t; i++) first[i]=-1,dgr[i]=0;}bool check(){    for (int i=1; i<=n; i++)        if (dgr[i]&1) return false;    return true;}void addedge(int U,int V,int W){    edge++;    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){    Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG;    while (bot<=top)    {        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])            if (c[i^1]>0 && tag[to[i]]!=TAG)            {                tag[to[i]]=TAG,d[to[i]]=d[cur]+1;                can[to[i]]=false,Q[++top]=to[i];                if (to[i]==s) return true;            }    }    return false;}int dfs(int cur,int num){    if (cur==t) return num;    int tmp=num,k;    for (int i=first[cur]; i!=-1; i=next[i])        if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]])        {            k=dfs(to[i],min(num,c[i]));            if (k) num-=k,c[i]-=k,c[i^1]+=k;            if (num==0) break;        }    if (num>0) can[cur]=true;    return tmp-num;}int main(){    int U,V,W;    scanf("%d",&T);    while (T--)    {        scanf("%d%d",&n,&m);        _init();        while (m--)        {            scanf("%d%d%d",&U,&V,&W);            dgr[U]--,dgr[V]++;            if (W==0) addedge(U,V,1);        }        if (!check())        {            puts("impossible");            continue;        }        for (int i=1; i<=n; i++)        {            if (dgr[i]==0) continue;            if (dgr[i]<0) addedge(s,i,-dgr[i]/2);            else            {                sum+=dgr[i]/2;                addedge(i,t,dgr[i]/2);            }        }        while (bfs()) ans+=dfs(s,inf);        if (ans==sum) puts("possible");            else puts("impossible");    }    return 0;}


联系
我们