「网络流 24 题」太空飞行计划

「网络流 24 题」太空飞行计划

输入问题:怎么输入实验需要的仪器,我给出来的解决方法是先直接读取的资助,然后直接把后面的一行读进来,最后用类似于优读的方法处理
题解:先建立一个源点和一个汇点,然后从源点向每个实验连边,边的容量为实验的资助,然后从仪器向汇点连边,同时从实验向对应的仪器连接一条容量为无限大的边。跑一边最大流。最后的残量图上仍然存在的仪器和实验,就是我们选择的仪器和实验
证明:我有一个对这个命题十分美妙的证明,这里空白太小,写不下。:)

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 1000000;

using namespace std;

int n,m,e = 2,s,t,sum;
int head[MAXN],d[MAXN],cur[MAXN];

vector<int>a,b;

string str;

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",&n,&m);
    int v;s = 0;t = n+m+1;
    for(int i = 1;i <= n;i++){
        scanf("%d",&v);sum += v;
        addedge(s,i,v);char ch = getchar();
        getline(cin,str);v = 0;
        for(int j = 0;j < str.length();j++){
            if('0' <= str[j] && str[j] <= '9') v = v * 10 + str[j] - '0';
            if(str[j] == ' ') {
                addedge(i,v+n,INF);
                v = 0;
            }
         }
         addedge(i,v+n,INF);
    }
    
    for(int i = 1;i <= m;i++){
        scanf("%d",&v);
        addedge(i+n,t,v);
    }
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    d[s] = 1;Q.push(s);
    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();
    
    sum -= max_flow();
    for(int i = 1;i <= n;i++) if(d[i]) a.push_back(i); 
    for(int i = 0;i < a.size();i++) printf(i != a.size() - 1 ? "%d " : "%d",a[i]);
    printf("\n");
    for(int i = 1;i <= m;i++) if(d[i+n]) b.push_back(i);     
    for(int i = 0;i < b.size();i++) printf(i != b.size() - 1 ? "%d " : "%d",b[i]);
    printf("\n");    
    printf("%d\n",sum);
    return 0;
} 
Last modification:October 5th, 2018 at 02:14 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment