【poj1637】Sightseeing tour

2015.05.26 20:40 Tue | 18次阅读 | 旧日oi | 固定链接 | 源码

题目大意:求混合图的欧拉回路,欧拉回路是啥自己百度- -,点数<=200,边数<=1000
题解
首先一个图存在欧拉回路的充分必要条件是每个点入度等于出度。对于一个混合图,我们可以任意定向无向边,记录每个点的入度和出度,如果和为奇数,无解。
然后我们考虑将一些边反向,反向一条边造成2的差距,所以我们把每个点的(入度-出度)/2,如果大于0,和原点连,如果小于零,和汇点连,然后把无向边按照之前定向的顺序加入网络,然后跑最大流,如果满流,说明有解,解就是将有流量的正向边反向之后和原有向边构成的图。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 1500
#define inf 0x3f3f3f3f
using namespace std;
int test,n,m,S,T,sum;
int u[N],v[N],d[N];
int in[N],out[N];
struct edge{
    int to,next,flow;
}e[50000];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);ae(v,u,0);
}
bool precheck()
{
    for(int i=1;i<=n;i++) if(abs(out[i]-in[i])&1) return 1;
    return 0;
}
queue<int> q;
int dis[N];
bool bfs()
{
    while(!q.empty()) q.pop();q.push(S);
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(e[i].flow,limit-cost));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit)break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) 
    ret+=dfs(S,inf);
    return ret;
}
int main()
{
    cin>>test;
    while(test--)
    {
        scanf("%d%d",&n,&m);
        S=0;T=n+1;sum=0;tp=0;
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(h,-1,sizeof(h));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u[i],&v[i],&d[i]);
            in[v[i]]++;out[u[i]]++;
        }
        if(precheck()) 
        {
            puts("impossible");
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            if(out[i]>in[i]) add(S,i,(out[i]-in[i])>>1),sum+=(out[i]-in[i])>>1;
            else if(in[i]>out[i]) add(i,T,(in[i]-out[i])>>1);
        }
        for(int i=1;i<=m;i++)
        if(!d[i]) add(u[i],v[i],1);
        if(dinic()==sum) puts("possible");
        else puts("impossible");
    }
}```