「网络流 24 题」试题库
题解:从源点向每个题目连接一条容量为1的边,从每个题型向汇点连接容量为需要题量的边,从每个题目向题型连接容量为1的边,跑一遍最大流。然后如果最大流等于每个题型需要的题数总和就有解,否则无解。
方案输出:每个题目属于自己满流对应的题型。直接加进去然后输出就好了

#include <bits/stdc++.h>

const int MAXN = 100000,INF = 10000000;

using namespace std;

int k,n,s,t,e = 2,ans;
int d[MAXN],cur[MAXN],head[MAXN];
string str;

vector<int>que[MAXN];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}

inline void init()
{
    scanf("%d%d",&k,&n);
    s = 0;t = k + n + 1;
    int v,sum; 
    for(int i = 1;i <= k;i++){
        scanf("%d",&v);ans += v;
        addedge(n+i,t,v);
    }
    
    for(int i = 1;i <= n;i++) addedge(s,i,1);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&sum);
        for(int j = 1;j <= sum;j++){
            scanf("%d",&v);
            addedge(i,n+v,1);
        }
    }
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1; 
                Q.push(E.v); 
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c - E.f,a))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            flow += f;
            a -= f;
            if(a == 0) break; 
        } 
    }
    return flow;
}

inline int max_flow(){
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

int main()
{
    
    init();

    ans -= max_flow();
    if(ans != 0) {printf("No Solution!");return 0;}
    
    for(int i = 1;i <= n;i++)
        for(int j = head[i];j;j = edge[j].next)
            if(edge[j].c == edge[j].f)
                que[edge[j].v-n].push_back(i);
    
    for(int i = 1;i <= k;i++) sort(que[i].begin(),que[i].end());
    
    for(int i = 1;i <= k;i++){
        printf("%d: ",i);
        for(int j = 0;j < que[i].size();j++)
            printf("%d ",que[i][j]);
        printf("\n");
    }
    
    return 0;
}
Last modification:October 7th, 2018 at 11:52 am
If you think my article is useful to you, please feel free to appreciate