1. 题目

传送门= ̄ω ̄=

2. 题解

前面发了这题的贪心解法,但是毕竟题目没给出总人数限制,所以不严谨。

这里再给出网络流解法吧。

建图的话就是从源点连一条容量为$r_i$的边到第$i$个单位,再从第$i$个桌子连一条容量为$c_i$的边到汇点,最后从每个单位连一条容量为1的边到每个桌子。

再跑最大流。

如果残量网络中有从源点到某个单位的边没有满流则说明无解,输出0。

否则对于每个单位,如果从该单位到某个桌子的原先容量为1的边满流了,则说明该单位用了这张桌子。

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct edge{int u,v,c;}e[100000];
int m,n,T,cnt,from[500];
bool book[505];
vector<int> g[500];
queue<int> que;
void adde(int a,int b,int c)
{
    g[a].push_back(cnt),e[cnt++]=(edge){a,b,c};
    g[b].push_back(cnt),e[cnt++]=(edge){b,a,0};
}
bool bfs()
{
    while(!que.empty())que.pop();
    memset(book,0,sizeof(book)),que.push(0),book[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(int i=0;i<g[F].size();i++)if(!book[e[g[F][i]].v]&&e[g[F][i]].c)
            from[e[g[F][i]].v]=g[F][i],que.push(e[g[F][i]].v),book[e[g[F][i]].v]=1;
        if(book[T])return 1;
    }
    return 0;
}
void mcf()
{
    int MX=INT_MAX;
    for(int i=from[T];i!=-1;i=from[e[i].u])MX=min(MX,e[i].c);
    for(int i=from[T];i!=-1;i=from[e[i].u])e[i].c-=MX,e[i^1].c+=MX;
}
int main()
{
    IN(m),IN(n),T=m+n+1,from[0]=-1;
    for(int i=1,a;i<=m;i++)IN(a),adde(0,i,a);
    for(int i=1,a;i<=n;i++)IN(a),adde(i+m,T,a);
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)adde(i,j+m,1);
    while(bfs())mcf();
    for(int i=1;i<=m;i++)if(book[i])puts("0"),exit(0);
    puts("1");
    for(int i=1;i<=m;i++,putchar('\n'))
        for(int j=0;j<g[i].size();j++)
            if(!e[g[i][j]].c)printf("%d ",e[g[i][j]].v-m);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *