第一次做这种”大型“网络流题（抱歉我是炒鸡大局若）。

注意同一个单位的人不可同桌聚餐，说明同一单位的人最多只能往某一桌子派一人！然后建图就很简单了：源点往每个单位连流量为[tex]r_i[/tex]的边，每个单位分别向每一个桌连一条流量为1的边，每个桌向汇点连一条流量为[tex]c_i[/tex]的边。跑一遍网络流即可。

这题坑点在于要输出解。输出解的时候注意不要把反向弧和正常的弧搞混。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=425;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};
int main(){
    int n,m,temp;
    bool flag;
    register int i,j,tag,end,Expect=0;
    freopen("roundtable.in","r",stdin);
    freopen("roundtable.out","w+",stdout);
    scanf("%d%d",&n,&m);
    end=n+m+1;
    REP_B(i,n){
        scanf("%d",&temp);
        Expect+=temp;
        Dinic::AddEdge(0,i,temp);
    }
    REP_B(i,m){
        scanf("%d",&temp);
        tag=i+n;
        Dinic::AddEdge(tag,end,temp);
        REP_B(j,n){
            Dinic::AddEdge(j,tag,1);
        }
    }
    temp=Dinic::Maxflow(0,end);
    if(temp<Expect){
        puts("0");
        return 0;
    }
    puts("1");
    REP_B(i,n){
        vector<int> V;
        REP(j,Dinic::G[i].size()){
            Edge& e=Dinic::edges[Dinic::G[i][j]];
            if(e.v>n && e.v<=m+n && e.cap==e.flow)
                V.push_back(e.v);
        }
        sort(V.begin(),V.end());
        flag=false;
        REP(j,V.size()){
            if(flag)
                putchar(' ');
            flag=true;
            printf("%d",V[j]-n);
        }
        putchar('\n');
    }
    return 0;
}

• 相关文章
• 全局相关文章