【LA3415 訓練指南】保守的老師 【二分圖最大獨立集，最小割】

題意

? Frank是一個思想有些保守的高中老師。有一次，他需要帶一些學生出去旅行，但又怕其中一些學生在旅行中萌生愛意。為了降低這種事情發生的概率，他決定確保帶出去的任意兩個學生至少要滿足下面四條中的一條。

1.身高相差大于40厘米

2.性別相同

3.最喜歡的音樂屬于不同類型

4.最喜歡的體育比賽相同

你的任務是幫助Frank挑選盡量多的學生，使得任意兩個學生至少滿足上述條件中的一條。

分析

?這個模型叫二分圖的最大獨立集。既選擇盡量多的結點，使得任意兩個結點不相鄰（既任意一條邊的兩個端點不會被同時選中）。最大獨立集與最小覆蓋是互補的，因此答案就是結點總數減去最大匹配數。

?建模：將每個人看作一個結點，如果兩個人四個條件都不滿足，就意味著他們不能同時被選擇，連一條無向邊。這樣，問題就轉換為求這個圖的最大獨立集。因為他們每個人不是男生就是女生，所以這個圖是二分圖。

?按照慣例，我依然是用網絡流來做的最大匹配。原因依然是不會KM···等哪天（8012年）我學會來并且心情好可能會來補一下KM的代碼。

??

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>

using namespace std;
const int maxn=1000+10;
const int maxm=2000000+100;

const int INF=2147000000;
struct Dinic{
    int head[maxn],Next[maxm],to[maxm],cap[maxm],flow[maxm];
    int sz,n,m,s,t;
    bool vis[maxn];
    int cur[maxn],d[maxn];
    void init(int n){
        this->n=n;
        memset(head,-1,sizeof(head));
        this->sz=-1;
    }
    void add_edge(int a,int b,int c){
        ++sz;
        to[sz]=b;
        cap[sz]=c;flow[sz]=0;
        Next[sz]=head[a];head[a]=sz;
        ++sz;
        to[sz]=a;
        cap[sz]=c;flow[sz]=c;
        Next[sz]=head[b];head[b]=sz;
    }
    bool BFS(){
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        vis[s]=1;
        d[s]=0;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();Q.pop();
            for(int i=head[u];i!=-1;i=Next[i]){
                int v=to[i];
                if(!vis[v]&&cap[i]>flow[i]){
                    vis[v]=1;
                    d[v]=d[u]+1;
                    Q.push(v);
                }
            }
        }
        return vis[t];
   }
    int DFS(int x,int a){
        if(x==t||a==0)return a;
        int Flow=0,f;
        for(int& i=cur[x];i!=-1;i=Next[i]){
            int v=to[i];
            if(d[v]==d[x]+1&&(f=DFS(v,min(a,cap[i]-flow[i])))>0){
                Flow+=f;
                flow[i]+=f;
                flow[i^1]-=f;
                a-=f;
                if(a==0)break;
            }
        }
        return Flow;
    }
    int Maxflow(int s,int t){
        this->s=s,this->t=t;
        int Flow=0;
        while(BFS()){
            for(int i=0;i<=n;i++)
             cur[i]=head[i];

            Flow+=DFS(s,INF);
        }
        return Flow;
    }
}dinic;
int T,n;
int high[maxn];
char sex[maxn];
string mus[maxn],phy[maxn];
int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d %c",&high[i],&sex[i]);
            cin>>mus[i]>>phy[i];
        }
        dinic.init(n+2);
        for(int i=1;i<=n;i++){
            if(sex[i]=='M'){
                for(int j=1;j<=n;j++){
                    if(sex[j]=='F'&&abs(high[i]-high[j])<=40&&mus[i]==mus[j]&&phy[i]!=phy[j]){
                            dinic.add_edge(i,j,1);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(sex[i]=='M')
                dinic.add_edge(0,i,1);
        }
        for(int i=1;i<=n;i++){
            if(sex[i]=='F')
                dinic.add_edge(i,n+1,1);
        }
        int ans=dinic.Maxflow(0,n+1);
        printf("%d\n",n-ans);
    }
return 0;
}

?

?? 其實我覺得這道題不知道這個模型只是考慮最小割的話也能想。去除最少的學生使得剩下的所有學生之間任意兩個之間都滿足四個條件中的一條。我們在學生之間連的邊是這兩個學生間只能選一個或者都不選，那個割掉這條邊就代表去掉這兩個學生中的一個。所以可以求出最小割來以后，用總的人數n減掉最小割。

? 哇萬能的最小割我感覺這樣想比背什么模型好多了啊！

?