[HAOI2017] 新型城市化

佚名 5年前 (2018-12-24) 算法 1057人围观抢沙发百度已收录

给出的图中恰包含2个团，则图的补图为一个二分图，其最大独立集为原图的最大团。

我们知道，二分图的最大独立集=V-最小顶点覆盖，最小顶点覆盖=最大匹配。

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

问题转化为：计算删去后最大匹配减小的边集。

所以建图跑最大流，对残余网络中的每一条满流边讨论。

这需要用到tarjan：若该满流边的端点同属一个强连通，那么通过该边的增广路不是必须的，这条边就不能算在答案里。

码吧。。建图时要利用二分图染色。

请务必启用-std=gnu++11开关

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N=1e4+5;
const int L=5e5+5;
const int inf=0x3f3f3f3f;

int S=N-1,T=N-2;
int head[N],to[L],upp[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int u1,int u2=0) {
    to[++cnt]=y,upp[cnt]=u1,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,upp[cnt]=u2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
int dfs(int x,int tf) {
    if(x==T) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,upp[i]));
        if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}

int n,m;
vector<int> e[N];
vector<pair<int,int>> ans;
int col[N],low[N],dfn[N],idx;
int sta[N],bel[N],tot,top;

void ran(int x) {
    for(int y: e[x]) if(!col[y])    
        col[y]=3^col[x], ran(y);
} 
void pre(int x) {
    dfn[x]=low[x]=++idx;
    sta[++top]=x;
    for(int i=head[x]; i; i=last[i]) if(upp[i]>0) {
        if(!dfn[to[i]]) {
            pre(to[i]);
            low[x]=min(low[x],low[to[i]]);
        } else if(!bel[to[i]]) 
            low[x]=min(low[x],dfn[to[i]]);
    }
    if(dfn[x]==low[x]) {
        tot++;
        do bel[sta[top]]=tot; while(sta[top--]!=x);
    }
}


int main() {
    scanf("%d%d",&n,&m);
    for(int x,y,i=m; i--; ) {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i=1; i<=n; ++i) {
        if(!col[i]) col[i]=1, ran(i);
    }
    for(int i=1; i<=n; ++i) {
        if(col[i]==1) {
            add_edge(S,i,1);
            for(int j:e[i]) add_edge(i,j,1);
        } else add_edge(i,T,1);
    }
    while(bfs()) dfs(S,inf);
    for(int i=1; i<=n; ++i) {
        if(!dfn[i]) pre(i);
    }
    if(!dfn[S]) pre(S);
    if(!dfn[T]) pre(T);
    for(int i=2; i<=cnt; i+=2) {
        if(upp[i]==0 && bel[to[i]]!=bel[to[i^1]] 
    && to[i]!=S && to[i]!=T && to[i^1]!=S && to[i^1]!=T) 
            ans.push_back(make_pair(to[i],to[i^1]));
    }
    for(pair<int,int> &p:ans) {
        if(p.first>p.second) swap(p.first,p.second); 
    }
    sort(ans.begin(),ans.end());
    printf("%llu\n",ans.size());
    for(pair<int,int> p:ans) {
        printf("%d %d\n",p.first,p.second);
    }
    return 0;
}