太空飞行计划问题

跟拍照几乎是重题。

在输出部分，若最后一次bfs还能到这个点，则可以输出。

只要有一个点可以从源点过得去，就可以通过正或反流到达所有经过的点。

但是我不明白若把所有项目都割掉了，那不就嘎嘎了。

这里也求广大读者说出自己的理解。

看代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6;
int n,m,sum;
int beg[maxn],nex[maxn],to[maxn],w[maxn],e;
inline void add(int x,int y,int z){
    nex[e]=beg[x];beg[x]=e;
    to[e]=y;w[e]=z;e++;
}
int dep[maxn],ans[maxn],top;
queue<int>q;
inline int bfs(){
    memset(dep,0x3f,sizeof(dep));
    while(!q.empty())q.pop();
    dep[0]=0;
    q.push(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=beg[x];~i;i=nex[i]){
            int t=to[i];
            if(w[i]&&dep[t]>10000){
                dep[t]=dep[x]+1;
                q.push(t);
            }
        }
    }
    return dep[n+m+1]<10000;
}
inline int dfs(int x,int lim){
    if(x==n+m+1||!lim)return lim;
    int ans=0;
    for(int i=beg[x];~i;i=nex[i]){
        int t=to[i];
        if(dep[t]==dep[x]+1){
            int f=dfs(t,min(lim,w[i]));
            ans+=f;lim-=f;
            w[i]-=f;w[i^1]+=f;
        }
    }
    return ans;
}
int main(){
    memset(beg,-1,sizeof(beg));
    cin>>m>>n;
    string s;
    //cout<<m<<" "<<n<<endl;
    getchar();
    for(int i=1;i<=m;i++){
        getline(cin,s);
        s+=' ';
        int x=0,flag=1;
        for(int j=0;j<s.size();j++){
            if(s[j]==' '){
                if(flag){
                    sum+=x;
                    add(0,i,x);
                    add(i,0,0);
                    x=flag=0;
                }else{
                    add(i,m+x,inf);
                    add(m+x,i,0);
                    x=0;
                }
            }else x=x*10+s[j]-'0';
        }
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        add(m+i,n+m+1,x);
        add(n+m+1,m+i,0);
    }
    while(bfs())sum-=dfs(0,inf);
    for(int i=1;i<=m;i++)
        if(dep[i]<10000)printf("%d ",i);
    puts("");
    for(int i=1;i<=n;i++)
        if(dep[i+m]<10000)printf("%d ",i);
    printf("
%d
",sum);
    return 0;
}

深深地感到自己的弱小。