[LOJ 6004] 圆桌聚餐

link

其实网络流就是再考你如何去建边。

先见$S$,$T$为源点与汇点，然后将$S$连向每一个单位，流量为每个单位的人数，然后将每一个单位连向每一个餐桌，流量为$1$，最后在将每一个餐桌与$T$相连，流量为每个餐桌容量，然后跑一边$Dinic$最大流就行，只需要优化一点点，每次$dfs$增广多条增广路就行，第一问就做完了($0$还是$1$)。第二问要去求到底在那一桌，我们可以去扫描当前的图，然后若$a$,$b$相连，且$a$为单位，$b$为餐桌，并且当前流量等于$0$,则必$a$集团的人道$b$桌吃饭，然后就输出就行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
queue<int> que;
const int MAXN=50001;
const int inf=INT_MAX;
struct node{
    int u,v,w,nex;
}x[MAXN<<1];
struct NODE{
    int edge,lst;
}pre[MAXN<<1];
int m,n,S,T,cnt,head[MAXN],num[MAXN],lim[MAXN],deep[MAXN];
void add(int u,int v,int w){
    x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;
}
bool bfs(){
    memset(deep,127/3,sizeof(deep));
    int INF=deep[1];
    while(!que.empty()) que.pop();
    deep[S]=1;que.push(S);
    while(!que.empty()){
        int xx=que.front();que.pop();
        for(int i=head[xx];i!=-1;i=x[i].nex){
            if(x[i].w&&deep[x[i].v]>deep[xx]+1){
                deep[x[i].v]=deep[xx]+1;
                que.push(x[i].v);
            }
        }
    }
    return deep[T]!=INF;
}
int ST,lowflow,ans,VIS;
inline int dfs(int xx,int flow){
    if(xx==T) {
        ans+=flow;
        VIS=1;
        return flow;
    }
    int used=0;
    for(int i=head[xx];i!=-1;i=x[i].nex){
        if(deep[x[i].v]==deep[xx]+1&&x[i].w){
            int slow=dfs(x[i].v,min(flow-used,x[i].w));
            if(slow){
                used+=slow;
                x[i].w-=slow;
                x[i^1].w+=slow;
                if(used==flow) break;
            }
        }
    }
    return used;
}
inline int dinic(){
    while(bfs()){
        VIS=1;
        while(VIS==1){
            VIS=0;
            dfs(S,inf);
        }
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    m=read(),n=read();
    S=0,T=n+m+2;
    for(int i=1;i<=m;i++){
        num[i]=read();add(S,i,num[i]),add(i,S,0);
        for(int j=1;j<=n;j++) add(i,j+m,1),add(j+m,i,0);
        ST+=num[i];
    }
    for(int i=1;i<=n;i++){
        lim[i]=read();
        add(i+m,T,lim[i]),add(T,i+m,0);
    }
    int st=dinic();
    if(st!=ST){printf("%d
",0);return 0;}
    printf("%d
",1);
    for(int i=1;i<=m;i++){
        for(int j=head[i];j!=-1;j=x[j].nex){
            if(x[j].v>=m+1&&x[j].v<=m+n+1&&!x[j].w){
                printf("%d ",x[j].v-m);
            }
        }
        printf("
");
    }
}