题解 P5295 【[北京省选集训2019]图的难题】

· · 题解

我看没有具体证明每个部分的，于是便来一发

更好的阅读享受：我的博客

首先你会发现一个性质：一个图符合条件当且仅当E<=2*V-2;

证明(简洁易懂)：

因为假设图中有2*V-2条边，为了符合条件，一定是有一颗白色生成树和一颗黑色生成树。可以看出，没有其他的情况；

那么如果再多一条边呢？显然，填在任意位置都会使任意一颗树变成基环树，导致一种颜色成环，不成立；

所以E的最大值就是2*V-2；

所以我们就是判断任意一个子图的E-2*V<=-2;

为了方便，我们只要判定一个E-2*V最大的子图是否<=-2就好了；

怎么求呢？这时候引入最大权闭合子图的概念就可以秒出答案了

首先来说最大权闭合子图的定义：

在一个有向图中，每个点都有一个点权：

　　闭合子图：对于这个子图，它任意一个点的的后继必须在这个子图中；　

　　最大权闭合子图：在所有的闭合子图中，该图的点权和最大； 求最大权闭合子图是标准的网络流建模模型；

　　首先我们建立超级源S和超级汇T；把所有点权为正的点与S连接一条有向边，方向是从S到u，边权是点权；把所有点权为负的点与T连接一条有向边，方向是从u到T，边权是点权的相反数；原图中所有有向边的边权是INT_MAX；

　　然后干什么呢？我们先看一看最大权闭合子图的定义：答案是(所有的正点权点的权值和-不在该图中的正点权点的权值和-在该图中负点权点的权值和)=(所有的正点权点的权值和-(不在该图中的正点权点的权值和+在该图中负点权点的权值和));

　　对于所有正点权点的权值和，我们可以简单的预处理出来，关键是后面的部分怎么求；

　　最小割的定义是在去除某些边后，S与T不连通，且去掉的边的权值和最小；

　　我们考虑一下割掉的边的定义：若割掉的边与S相连，那么表示这条边所对应的点u不在最大权闭合子图中；若割掉的边与T相连，那么表示这条边所对应的点u在最大权闭合子图中；注意：所有割掉的边一定与S或T相连；

假设S与T联通，那么一定存在一个点对(x,y),使得S到x有边，y到T有边，且存在一条x到y的路径；因为S到x有边，那么x在最大权闭合子图中，因为y到T有边，那么y不在最大权闭合子图中；而y一定是x的后继，所以y一定在最大权闭合子图中，这与之前的定义矛盾，所以条件不成立，S与T不连通；

　　所以最小割就是(不在该图中的正点权点的权值和+在该图中负点权点的权值和);

　　这就是后半部分的答案了；

　　所以最大权闭合子图的权值和就是所有点的点权和-该生成图的最小割；

然后回到本题:

把边化成点，点权为1，原来图中的点的点权是-2

因为选边就一定要选择点，所以所有选择的点的后继一定要都被选择；

然后就构成了最大权闭合子图的模型；

注意一个细节，需要枚举所有点表示强制选这个点，否则答案是不成立的；

如果还有不懂得可以私信我或者直接回复就可以；

代码放不放呢？还是放上吧；因为有些人调不过来的时候可以参考参考；

但是最好不要直接复制，因为当你复制题解的时候就是你退役的时候；

#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
class littlestar{
    public:     
        int to;
        int w;
        int nxt;
        void add(int u,int v,int gg);
}star[100010];
int head[100010],cnt=1;
inline void littlestar::add(int u,int v,int gg)
{
    to=v;
    nxt=head[u];
    head[u]=cnt;
    w=gg;
}
template<class nT>
inline void read(nT &x)
{
    char c;
    while(c=getchar(),!isdigit(c));
    x=c^48;
    while(c=getchar(),isdigit(c)) x=x*10+c-48;
}
int S,T;
int dis[100010];
int n,m;
bool bfs()
{
    memset(dis,0,sizeof(dis));
    queue<int> q;
    q.push(S);
    dis[S]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(!dis[v]&&star[i].w){
                dis[v]=dis[u]+1;
                q.push(v);
                if(v==T) return 1;
            }
        }
    }
    return 0;
}
int dinic(int u,int flow)
{
    if(u==T) return flow;
    int rest=flow,tmp;
    for(int i=head[u];i&&rest;i=star[i].nxt){
        int v=star[i].to;
        if(dis[v]==dis[u]+1&&star[i].w){
            tmp=dinic(v,min(star[i].w,rest));
            if(!tmp) dis[v]=0;
            star[i].w-=tmp;
            star[i^1].w+=tmp;
            rest-=tmp;
        }       
    }
    return flow-rest;
}
int sum=0;
int tmpu[10000],tmpv[10000];
int myenum(int s)
{
    memset(head,0,sizeof(head));
    cnt=1;
    inc(i,1,m){
        int u,v;
        u=tmpu[i]; v=tmpv[i];
        star[++cnt].add(S,i,1);
        star[++cnt].add(i,S,0);
        star[++cnt].add(i,m+u,INT_MAX);
        star[++cnt].add(m+u,i,0);
        star[++cnt].add(i,m+v,INT_MAX);
        star[++cnt].add(m+v,i,0);
    }
    inc(i,1,n){
        if(s==i) continue;
        star[++cnt].add(i+m,T,2);
        star[++cnt].add(T,i+m,0);
    }
    sum=m-2;
    while(bfs()){
        sum-=dinic(S,INT_MAX);
    }
    return sum;
}
int main()
{
    int tt;
    read(tt);
    while(tt--){
        read(n); read(m);
        S=n+m+1,T=n+m+2;
        int ans=-INT_MAX;
        inc(i,1,m) read(tmpu[i]),read(tmpv[i]);
        for(int i=1;i<=n;i++){
            ans=max(ans,myenum(i));
        }
        if(ans+2>0){
            cout<<"No"<<endl;
        }
        else{
            cout<<"Yes"<<endl;
        }
    }
}