最大流dinic RE最后3个点求调♂教
查看原帖
最大流dinic RE最后3个点求调♂教
275989
LingHusama楼主2023/7/30 08:18
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
#define int long long
struct node{
    int to;
    int left;
    int mx;
    int rev;
};
vector<node>mp[505];
int dep[505];
bool bfs(){
    memset(dep,-1,sizeof(dep));
    queue<int>q;
    dep[s]=1;
    q.push(s);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<mp[u].size();i++){
            int to=mp[u][i].to;
            if(dep[to]==-1&&mp[u][i].left>0){
                q.push(to);
                dep[to]=dep[u]+1;
            }
            
        }
    }
    if(dep[t]!=-1){
        return 1;
    }
    else{
        return 0;
    }
}
int dfs(int x,int val){
    if(x==t||!val){
        return val;
    }
    int tmp=0;
    for(int i=0;i<mp[x].size();i++){
        int to=mp[x][i].to;
        if(mp[x][i].left>0&&dep[to]==dep[x]+1){
            int flow=dfs(to,min(val,mp[x][i].left));
            val-=flow;
            int posb=mp[x][i].rev;
            mp[to][posb].left+=flow;
            mp[x][i].left-=flow;
            tmp+=flow;
            if(!val){
                break;
            }
        }
        
    }
    if(!tmp){
        dep[x]=-1;
    }
    return tmp;

}
int dinic(){
    int ret=0;
    while(bfs()){
        ret+=dfs(s,n);
    }
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    s=0;
    t=n+m+1;
    for(int j=1;j<=n;j++){
        int ss;
        cin >> ss;
        for(int i=1;i<=ss;i++){
            int to;
            cin >> to;
            to+=n;//这里会占用到M的点位 
            int apos=mp[to].size();
            int bpos=mp[j].size();
            mp[j].push_back((node){to,1,1,bpos});//虽然边有限制了,但流到这个点的值可能不是1。
            mp[to].push_back((node){j,0,1,apos});
        }//已经占用1-N+M的点了
        
    }
    for(int i=1;i<=n;i++){//创建0这个虚拟源点,按照规律,他肯定可以流完所有的1-n的点
        int apos=mp[0].size();
        int bpos=mp[i].size();
        mp[0].push_back((node){i,1,1,bpos});
        mp[i].push_back((node){0,0,1,apos});
    }
    int v=n+m+1;
    for(int i=1;i<=m;i++){//利用拆点进行点的限制,虽然存在点和点挤的情况,但最大流算法是可以反悔的!
        int u=i+n; 
        int apos=mp[u].size();
        int posb=mp[v].size();
        mp[u].push_back((node){v,1,1,posb});//这个才是点的限制,本题关键,但是由于都是1,直接连接超级汇点即可
        mp[v].push_back((node){u,0,1,apos});
    }
//    cout<<mp[v].size()<<endl; 
    cout<<dinic();
}
2023/7/30 08:18
加载中...