二分图与网络流初步

用户头像 发布于 2025-08-15 47 次阅读 OI

S+二分图与网络流初步

A. 生成二分图

找出所有的二分图，
对于每个二分图自己，所有的连接方案肯定是两种颜色的乘积的两倍，
而单个二分图中每个点都可以与其他二分图的点相连，因为会重复计算，所以不用乘二。
最后因为 $(u,v)$ 等价于 $(v,u)$，
所以把所有合法的边数除以 $2$ 再减去已经有了的边数 $m$ 就能得到答案。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,ans,y=1;
int col[N],cnt[3];
vector<int> g[N];
void dfs(int u,int c){
    col[u]=c,cnt[c]++;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(col[v]==c) y=0;
        if(col[v]) continue;
        dfs(v,3-c);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!col[i]){
            cnt[1]=cnt[2]=0;
            dfs(i,1);
            ans+=cnt[1]*cnt[2]*2+(cnt[1]+cnt[2])*(n-cnt[1]-cnt[2]);
        }
    }
    if(!y) cout<<0;
    else cout<<ans/2-m;
    return 0;
}
C++

B. 图上同色最远

可以贪心想到，在“简单路径”上，
相邻的点最好不能染同样的颜色，
而题意正是使简单路径的最小值最大，
所以可以二分出 $X$，
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
struct node{
    int v,w;
};
int n,m;
int col[N],w1[N],w2[N];
vector<node> g[N];
void findw(int u,int w){
    if(w<w1[u]) w2[u]=w1[u],w1[u]=w;
    else if(w<w2[u]&&w>=w1[u]) w2[u]=w;
}
bool dfs(int u,int x,int c){
    col[u]=c;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i].v,w=g[u][i].w;
        if(w>=x) continue;
        if(col[v]==col[u]) return 0;
        if(!col[v]&&!dfs(v,x,3-c)) return 0;
    }
    return 1;
}
bool check(int x){
    memset(col,0,sizeof col);
    for(int i=1;i<=n;i++) if(!col[i]){
        if(!dfs(i,x,1)) return 0;
    }
    return 1;
}
signed main(){
    memset(w1,0x3f,sizeof w1);
    memset(w2,0x3f,sizeof w2);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        findw(u,w),findw(v,w);
    }
    int l=0,r=LONG_LONG_MAX,ans;
    for(int i=1;i<=n;i++) r=min(r,w1[i]+w2[i]);
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        } 
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}
C++

C. 树上奇偶距离

可以发现，数一定是二分图，
而距离是偶数时，两点同色，
距离是奇数时，两点异色。
根据性质建树即可，但是细节比较多，
（去重写的有点麻烦了，甚至多此一举写了一个重载运算符）
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
int n;
struct node{
    int x,y;
    bool operator ==(node &a){
        return a.x==x&&a.y==y;
    }
};
vector<int> t[N],sg[N],ug[N],sum[3];
vector<node> ans;
char a[N][N];
int col[N];
bool dfs(int u,int c){
    col[u]=c;
    for(int i=0;i<sg[u].size();i++){
        int v=sg[u][i];
        if(!col[v]&&!dfs(v,c)) return 0;
        if(col[v]!=c) return 0;
    }
    for(int i=0;i<ug[u].size();i++){
        int v=ug[u][i];
        if(!col[v]&&!dfs(v,3-c)) return 0;
        if(col[v]==c) return 0;
    }
    return 1;
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){
        if(a[i][j]=='E'){
            sg[i].push_back(j);
            sg[j].push_back(i);
        }
        else if(a[i][j]=='O'){
            ug[i].push_back(j);
            ug[j].push_back(i);
        }
    }
    if(!dfs(0,1)){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<n;i++){
        if(!col[i]) if(!dfs(i,2)){
            cout<<-1;
            return 0;
        }
    }
    for(int i=0;i<n;i++) sum[col[i]].push_back(i);
    if(!sum[1].size()||!sum[2].size()){
        cout<<-1;
        return 0;
    }
    for(int i=0;i<sum[2].size();i++){
        int x=sum[1][0],y=sum[2][i];
        if(x>y) swap(x,y);
        ans.push_back((node){x,y});
    } 
    for(int i=0;i<sum[1].size();i++){
        int x=sum[2][0],y=sum[1][i];
        if(x>y) swap(x,y);
        ans.push_back({x,y});
    } 
    for(int i=0;i<ans.size();i++){
        for(int j=0;j<ans.size();j++){
            if(i==j) continue;
            node x=ans[i],y=ans[j];
            if(x==y&&x.x+x.y!=0) ans[i].x=ans[i].y=0;
        }
    }
    for(int i=0;i<ans.size();i++){
        node x=ans[i];
        if(x.x!=0||x.y!=0) cout<<x.x<<" "<<x.y<<" ";
    }
    return 0;
}
C++