题目大意

给你一个有向图,初始无边,给你N个三元组(X,Y,Z)表示有一条边从X发出,要么连向Y,要么连向Z.请你合理安排并输出一种方案使得每个点的入度和出度相等。


易知每个点的出度是确定的,所以只是需要求出一个方案使得每个点的入度恰好等于相关值。所以考虑使用Dinic求二分图完美匹配。

建立一个二分图,建出关系点,连向Y,Z,每个实点连向T,跑一遍看一下剩余流量是不是0,如果是表明必须用它。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxN 1000010
#define INF 1<<30
int n,m,inx,iny,inz,S,T,ans[maxN],depth[maxN],cnt[maxN];
int to[maxN<<1],nex[maxN<<1],val[maxN<<1],head[maxN],tot=1;
queue<int>q;
bool bfs()
{
    memset(depth,-1,sizeof depth);
    depth[S]=0;
    while(!q.empty()) q.pop();
    q.push(S);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i;i=nex[i])
            if(val[i]&&depth[to[i]]==-1)
            {
                depth[to[i]]=depth[tmp]+1;
                if(to[i]==T) return true;
                q.push(to[i]);
            }
    }
    return false;
}
int dinic(int pos,int left)
{
    if(pos==T) return left;
    int nleft=left;
    for(int i=head[pos];i;i=nex[i])
        if(val[i]&&depth[to[i]]==depth[pos]+1)
        {
            int tmp=dinic(to[i],min(nleft,val[i]));
            if(!tmp) depth[to[i]]=-1;
            nleft-=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            if(!nleft) break;
        }
    return left-nleft;
}
void addedge(int tx,int ty,int tz)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;
    to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    S=0,T=n+m+1;
    for(int i=1;i<=m;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(S,i,1),addedge(i,iny+m,1),addedge(i,inz+m,1),++cnt[inx];
    for(int i=1;i<=n;++i) addedge(i+m,T,cnt[i]);
    while(bfs()) dinic(S,INF);
    for(int i=1;i<=m;++i)
    {
        if(!val[head[i]]) ans[i]=1;
        else if(!val[nex[head[i]]]) ans[i]=0;
    }
    for(int i=1;i<=m;++i) printf("%d",ans[i]);
}