Luogu5295 图的难题 | Arahc's Home

题面

简化题意

给定一个无向图，将边黑白染色。求是否存在一种方案使得不存在同色环。

$n\leq501,m\leq 2n$ 。

题解

先摆上一个很显然的性质：一个合法的图一定满足 $m\leq 2n-2$ 。

为什么？考虑建一个白边树和一个黑边树，此时再加任意一条边都会使得一种颜色有环。

这个是不是充要呢？显然不是，考虑如下这个图：

原图满足 $m\leq 2n-2$ ，但是它的一个子图不满足。因此只有一个图的所有子图都满足 $m\leq 2n-2$ 时才有合法方案。至于怎么构造，不就是一个白树一个黑树嘛。

对于每条边建立一个点，权值为 $1$ ，原图的点的权值为 $-2$ 。因为选择了边对应的点就一定要选择其连接的点，因此原问题变成了一个最大权闭合子图问题，网络流即可。

注意到选出来的子图不能是空集，所以需要枚举一个必须选的点再跑网络流。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=2003,max_m=200005,inf=1000000000;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
    int nx[max_m*2],to[max_m*2],ln[max_m*2],hd[max_n],ct;
    graph(){ct=1;}
    inline void clear(){
        ct=1;
        memset(hd,0,sizeof(hd));
    }
    inline void add(int u,int v,int w){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
        nx[++ct]=hd[v],hd[v]=ct,to[ct]=u,ln[ct]=0;
    }
}e;

int n,m,S,T,U[max_n],V[max_n];

queue<int> q;
int cr[max_n],c[max_n];
inline bool bfs(){
    q.push(S);
    memset(c,-1,sizeof(c)),c[S]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(register int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(c[v]!=-1 || !e.ln[i]) continue;
            c[v]=c[u]+1,
            q.push(v);
        }
    }
    return c[T]!=-1;
}
inline int dfs(int u,int fl){
    if(u==T) return fl;
    int res=0;
    for(register int &i=cr[u];i && res<fl;i=e.nx[i]){
        int v=e.to[i];
        if(c[v]!=c[u]+1 || !e.ln[i]) continue;
        int tmp=dfs(v,min(e.ln[i],fl-res));
        if(tmp>0){
            res+=tmp;
            e.ln[i]-=tmp,
            e.ln[i^1]+=tmp;
        }
        else c[v]=-1;
    }
    return res;
}

inline int dinic(){
    int res=0;
    while(bfs()){
        for(register int i=1;i<=T;++i)
            cr[i]=e.hd[i];
        int x=dfs(S,inf);
        while(x>0) res+=x,x=dfs(S,inf);
    }
    return res;
}

inline int sol(int p){
    e.clear();
    for(register int i=1;i<=m;++i){
        int u=U[i],v=V[i];
        e.add(S,i+n,1),
        e.add(i+n,u,inf),
        e.add(i+n,v,inf);
    }
    for(register int i=1;i<=n;++i) if(i!=p)
        e.add(i,T,2);
    return m-dinic();
}

signed main(){
    for(register int TT=read();TT;--TT){
        n=read(),m=read(),S=n+m+1,T=S+1;
        for(register int i=1;i<=m;++i)
            U[i]=read(),V[i]=read();
        int ans=sol(1);
        for(register int i=2;i<=n;++i)
            ans=max(ans,sol(i));
        puts(ans<=0?"Yes":"No");
    }
    return 0;
}