题解 P3254 【圆桌问题】

fmx0219 · 2019-04-27 19:23:08 · 题解

这题其实还比较简单 第一问可以用网络流来写，用s-单位-餐桌-t的建图方式即可，s-单位的容量为单位代表数，单位-餐桌容量为1，餐桌-t容量为餐桌的容； 第二问可以用贪心来写； 附代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int inf=1<<30;
int a[160];
struct nod
{
    int x,y;
}b[300];
bool cmp(nod a,nod b)
{
    return a.x>b.x;
}
int pre[10005];
struct node
{
    int ver;
    int val;
    int next;
}e[300005];
int h[300005],cnt=1,d[30005];
queue<int> q;
void add(int x,int y,int z)
{
    e[++cnt].ver=y;
    e[cnt].val=z;
    e[cnt].next=h[x];
    h[x]=cnt;
    e[++cnt].ver=x;
    e[cnt].val=0;
    e[cnt].next=h[y];
    h[y]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();
    q.push(s);d[s]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].next)
        {
            int y=e[i].ver;
            if(e[i].val&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int x,int y)
{
    if(x==t)
    {
        return y;
    }
    int r=y,k;
    for(int i=h[x];i&&r;i=e[i].next)
    {
        int yy=e[i].ver;
        if(e[i].val&&d[yy]==d[x]+1)
        {
            pre[x]=yy;
            k=dfs(yy,min(e[i].val,r));
            e[i].val-=k;
            e[i^1].val+=k;
            r-=k;
        }
    }
    return y-r;
}
int main()
{
    cin>>n>>m;
    int sun=0;
    t=n+m+1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        add(s,i,a[i]);
        sun+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            add(i,j+n,1);
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i].x;
        add(i+n,t,b[i].x);
        b[i].y=i;
    }
    int f=0,ans=0;
    while(bfs())
    {
        while((f=dfs(s,inf)))
        {
            ans+=f;
        }
    }
    if(ans!=sun) 
    {
        cout<<'0';
        return 0;
    }
    cout<<'1'<<endl;
    for(int i=1;i<=n;i++)
    {
        sort(b+1,b+1+m,cmp);
        for(int j=1;j<=a[i];j++)
        {
            b[j].x--;
            cout<<b[j].y<<' ';
        }
        cout<<endl;
    }
    return 0;
}