[HAOI2017]新型城市化

题目

发现题目给了一张补图，求的是最大团

而且隐隐约约告诉我们这张补图是一个二分图

于是非常自然联想到最大团等于补图最大独立集

最大独立集又等于总点数-最小点覆盖

最小点覆盖=最大匹配

使得最大团增加就需要使得最大匹配减小

于是我们终于读懂题目了，就是求二分图匹配的必须边

直接在残量网络里跑\(tarjan\)，就是如果这条边没有满流就连上

对于一条边\((x,y)\)

如果\((x,y)\)是一条匹配边或者\(x\)，\(y\)在同一个强联通分量里，那么这就是一条最大匹配的可行边

如果\((x,y)\)是一条匹配边并且\(x\)，\(y\)不在同一个强连通分量里，那么这就是一条必须边

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define re register
#define mp std::make_pair
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=12005;
const int inf=1e9;
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,f;}e[500005];
int n,m,num=1,S,T;
std::queue<int> q;
int head[maxn],d[maxn],cur[maxn],co[maxn];
inline void C(int x,int y,int f) {
    e[++num].v=y;e[num].f=f;
    e[num].nxt=head[x];head[x]=num;
}
inline void add(int x,int y,int f) {C(x,y,f);C(y,x,0);}
inline int BFS() {
    for(re int i=S;i<=T;i++) d[i]=0,cur[i]=head[i];
    d[S]=1,q.push(S);
    while(!q.empty()) {
        int k=q.front();q.pop();
        for(re int i=head[k];i;i=e[i].nxt)
        if(!d[e[i].v]&&e[i].f) d[e[i].v]=d[k]+1,q.push(e[i].v);
    }
    return d[T];
}
int dfs(int x,int now) {
    if(x==T||!now) return now;
    int flow=0,ff;
    for(re int& i=cur[x];i;i=e[i].nxt)
    if(e[i].f&&d[e[i].v]==d[x]+1) {
        ff=dfs(e[i].v,min(e[i].f,now));
        if(ff<=0) continue;
        now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;
        if(!now) break;
    }
    return flow;
}
std::vector<int> ee[maxn];
namespace Tarjan {
    std::vector<int> v[maxn];
    int dfn[maxn],low[maxn],col[maxn],st[maxn],f[maxn];
    int top,p,cnt,mid,tot;
    std::pair<int,int> ans[150005];
    void tarjan(int x) {
        dfn[x]=low[x]=++cnt;
        f[x]=1,st[++top]=x;
        for(re int i=0;i<v[x].size();++i) {
            int j=v[x][i];
            if(!dfn[j]) tarjan(j),low[x]=min(low[x],low[j]);
            else if(f[j]) low[x]=min(low[x],dfn[j]);
        }
        if(dfn[x]==low[x]) {
            ++p;
            do {
                mid=st[top--];
                f[mid]=0;
                col[mid]=p;
            }while(mid!=x);
        }
    }
    void solve() {
        for(re int i=S;i<=T;i++)
            for(re int j=head[i];j;j=e[j].nxt)
            if(e[j].f) v[i].push_back(e[j].v);
        for(re int i=S;i<=T;i++) if(!dfn[i]) tarjan(i);
        for(re int i=1;i<=n;i++) {
            if(co[i]) continue;
            for(re int j=head[i];j;j=e[j].nxt)
            if(col[i]!=col[e[j].v]&&!e[j].f&&e[j].v!=S) {
                int xx=min(i,e[j].v);
                int yy=max(i,e[j].v);
                ans[++tot]=mp(xx,yy);
            }
        }
        std::sort(ans+1,ans+tot+1);
        printf("%d\n",tot);
        for(re int i=1;i<=tot;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    }
}
void paint(int x,int c) {
    co[x]=c;
    for(re int i=0;i<ee[x].size();i++) {
        int j=ee[x][i];
        if(co[j]!=2) continue;
        paint(j,c^1);
    }
}
int main() {
    n=read(),m=read();T=n+1;
    for(re int x,y,i=1;i<=m;i++) 
        x=read(),y=read(),ee[x].push_back(y),ee[y].push_back(x);
    for(re int i=1;i<=n;i++) co[i]=2;
    for(re int i=1;i<=n;i++)
    if(co[i]==2) paint(i,0);
    for(re int i=1;i<=n;i++) 
    if(!co[i]) add(S,i,1);else add(i,T,1);
    for(re int i=1;i<=n;i++) {
        if(co[i]) continue;
        for(re int j=0;j<ee[i].size();j++) 
            add(i,ee[i][j],1);
    }
    while(BFS()) dfs(S,inf);
    Tarjan::solve();
    return 0;
}

[HAOI2017]新型城市化

原文：https://www.cnblogs.com/asuldb/p/10608216.html