poj1637 Sightseeing tour

佚名 5年前 (2019-04-22) 随笔 2202人围观抢沙发百度已收录

题目描述：

poj

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解：

最大流+欧拉回路简单的性质。

有向图存在欧拉回路当且仅当每个点入度等于出度。

那么就很好办了，给出所有边，每个点入度+出度已知，先判一波度数。

然后边和点有二分图的关系，求一下最大匹配是否等于$0$的数量就好了。

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1500;
const int inf = 0x3f3f3f3f;
const ll  Inf = 0x3f3f3f3f3f3f3f3fll;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
int _,n,m,hed[N],cnt=1,S,T,ind[N],smd[N],pe[N][2],tot;
struct EG
{
    int to,nxt;
    ll fl;
}e[10050];
void ae(int f,int t,ll fl)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    e[cnt].fl = fl;
    hed[f] = cnt;
}
void AE(int f,int t,ll fl)
{
    ae(f,t,fl);
    ae(t,f,0);
}
void clear()
{
    memset(hed,0,sizeof(hed));
    memset(ind,0,sizeof(ind));
    memset(smd,0,sizeof(smd));
    cnt = 1;tot = 0;
    S = n+m+1,T = S+1;
}
int cur[N],dep[N];
bool vis[N];
bool bfs()
{
    queue<int>q;
    memcpy(cur,hed,sizeof(cur));
    memset(dep,0x3f,sizeof(dep));
    dep[S] = 0,vis[S] = 1;q.push(S);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int j=hed[u];j;j=e[j].nxt)
        {
            int to = e[j].to;
            if(e[j].fl&&dep[to]>dep[u]+1)
            {
                dep[to] = dep[u]+1;
                if(!vis[to])vis[to]=1,q.push(to);
            }
        }
        vis[u]=0;
    }
    return dep[T]!=inf;
}
ll dfs(int u,ll lim)
{
    if(u==T||!lim)return lim;
    ll fl = 0,f;
    for(int j=cur[u];j;j=e[j].nxt)
    {
        cur[u] = j;
        int to = e[j].to;
        if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].fl))))
        {
            fl+=f,lim-=f;
            e[j].fl-=f,e[j^1].fl+=f;
            if(!lim)break;
        }
    }
    return fl;
}
ll dinic()
{
    ll ret = 0;
    while(bfs())
        ret+=dfs(S,Inf);
    return ret;
}
int main()
{
//    freopen("tt.in","r",stdin);
    read(_);
    while(_--)
    {
        read(n),read(m);
        clear();
        for(int l,r,op,i=1;i<=m;i++)
        {
            read(l),read(r),read(op);
            smd[l]++,smd[r]++;
            if(op)ind[l]++;
            else pe[++tot][0]=l,pe[tot][1]=r;
        }
        bool ORZ = 0;
        for(int i=1;!ORZ&&i<=n;i++)
            if((smd[i]&1)||(ind[i]*2>smd[i]))ORZ=1;
        if(ORZ)
        {
            puts("impossible");
            continue;
        }
        for(int i=1;i<=tot;i++)
        {
            AE(S,i,1);
            AE(i,tot+pe[i][0],1);
            AE(i,tot+pe[i][1],1);
        }
        for(int i=1;i<=n;i++)
            AE(tot+i,T,smd[i]/2-ind[i]);
        puts(dinic()==(ll)tot?"possible":"impossible");
    }
    return 0;
}