试题库问题
我以后！一定！好好读题！（流下悲伤的泪水）
为了避免更多小可爱误解这道题的题意
我重新复述一遍这个题的题意TAT
我们现在有n道题并且每道题有p个属性可以归属 共计k个属性 要求对于每一种属性选出ai道题
首先一道题只能归属一个属性 所有属性之间互相独立
TAT
我在来偷偷说说我读的版本。。。
每一道题选了对于他所属的p个属性都有1的贡献 一共要选m道题 问你方案TAT
我死活建不出模来然后一看题解这玩意怎么不大对劲啊。。。
然后发现我读错了题QAQ
一个爆哭呜呜呜
所以对于正确的题意来说，建模非常简单啦。
我们对每一道题可以向他的所有属性连流量为1的边，因为每道题只能选择一次所以源点向每道题连流量为1的边。最后因为每个属性的选题数目已经给出所以直接向t连流量为ai的边即可。
最后跑最大流看是否满足选出的题数为m就可以了
方案直接枚举每个点然后看流空即可QwQ
附代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 20021225
#define ll long long
#define mxn 1000001
using namespace std;
struct edge{int to,lt,f;}e[mxn<<1];
int in[mxn],cnt=1,dep[mxn],s,t;
void addedge(int x,int y,int f)
{
e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;in[x]=cnt;
e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].f=0;in[y]=cnt;
}
queue<int> que;
bool bfs()
{
while(!que.empty()) que.pop();
memset(dep,0,sizeof(dep));
dep[s]=1;que.push(s);
while(!que.empty())
{
int x=que.front();que.pop();
for(int i=in[x];i;i=e[i].lt)
{
int y=e[i].to;
if(!dep[y]&&e[i].f)
{
dep[y]=dep[x]+1;
if(y==t) return 1;
que.push(y);
}
}
}
return 0;
}
int dfs(int x,int flow)
{
if(x==t||!flow) return flow;
int cur=flow;
for(int i=in[x];i;i=e[i].lt)
{
int y=e[i].to;
if(dep[y]==dep[x]+1&&e[i].f)
{
int tmp=dfs(y,min(cur,e[i].f));
e[i].f-=tmp;e[i^1].f+=tmp;cur-=tmp;
if(!cur) break;
}
}
dep[x]=-1;
return flow-cur;
}
int dinic()
{
int ans=0;
while(bfs())
ans+=dfs(s,inf);
return ans;
}
int w[21];
int main()
{
int k,n,i,p,a,j,m=0;
scanf("%d%d",&k,&n);s=n+k+1;t=s+1;
for(i=1;i<=k;i++)
scanf("%d",&w[i]),m+=w[i],addedge(i,t,w[i]);
for(i=1;i<=n;i++)
{
addedge(s,i+k,1);
scanf("%d",&p);
for(j=1;j<=p;j++)
{
scanf("%d",&a);//printf("***%d %d
",i+k,a);
addedge(i+k,a,1);
}
}
if(dinic()<m)
printf("No Solution!
");
else
{
for(i=1;i<=k;i++)
{
printf("%d: ",i);
for(j=in[i];j;j=e[j].lt)
{
if(e[j].to==t) continue;
if(e[j].f) printf("%d ",e[j].to-k);
}
printf("
");
}
}
return 0;
}