传送门

显然的网络流,源点向所有题目连流量为1的边,表示一题只能用一次,题目向它的所有类型连边,流量设为1,类型向汇点连边流量为题目需要的该类型的数量

然后最大流

如果最大流小于总需要的类型题目数量则无解,否则说明有解

考虑找出方案,显然如果一题到一个类型的边被流了,那么这题就是用来当成该类型来用

枚举所有类型和它的反向边,如果反向边有流量(即正向边被流了),那么输出反向边连接的题目

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=1e5+,INF=1e9+;
int fir[N],from[N<<],to[N<<],val[N<<],cntt=;
inline void add(int a,int b,int c)
{
from[++cntt]=fir[a]; fir[a]=cntt;
to[cntt]=b; val[cntt]=c;
from[++cntt]=fir[b]; fir[b]=cntt;
to[cntt]=a; val[cntt]=;
}
int n,m,sum,S,T;
queue <int> q;
int Fir[N],dep[N];
bool BFS()
{
for(int i=;i<=T;i++) dep[i]=,Fir[i]=fir[i];
q.push(S); dep[S]=;
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=fir[x];i;i=from[i])
{
int &v=to[i]; if(dep[v]||!val[i]) continue;
dep[v]=dep[x]+; q.push(v);
}
}
return dep[T]>;
}
int DFS(int x,int mif)
{
if(x==T||!mif) return mif;
int fl=,res;
for(int i=Fir[x];i;i=from[i])
{
Fir[x]=i;
int &v=to[i]; if(dep[v]!=dep[x]+||!val[i]) continue;
if( res=DFS(v,min(mif,val[i])) )
{
fl+=res; mif-=res;
val[i]-=res; val[i^]+=res;
if(!mif) break;
}
}
return fl;
}
int Dinic()
{
int res=;
while(BFS()) res+=DFS(S,INF);
return res;
}
int main()
{
m=read(); n=read(); S=; T=n+m+;
int a;
for(int i=;i<=m;i++)
{
a=read(); sum+=a;
add(n+i,T,a);
}
for(int i=;i<=n;i++)
{
add(S,i,); a=read();
for(int j=;j<=a;j++) add(i,n+read(),);
}
if(Dinic()!=sum) { printf("No Solution!"); return ; }
for(int i=;i<=m;i++)
{
printf("%d:",i);
for(int j=fir[n+i];j;j=from[j])
{
int &v=to[j]; if(v==T||!val[j]) continue;
printf(" %d",v);
} putchar('\n');
}
return ;
}

最新文章

  1. 【iCore3应用开发平台】发布 iCore3 应用开发平台出厂代码rev0.0.5
  2. x01.Lab.StoreApp: XP 停服,微软变脸
  3. EXTJS 资料 combo 点一次触发一次
  4. linux远程执行命令
  5. (转)PHP函数spl_autoload_register()用法和__autoload()介绍
  6. [HDU 1535]Invitation Cards[SPFA反向思维]
  7. DIV+CSS规范命名
  8. SWT的选择文件和文件夹的函数
  9. freemarker报错之十三
  10. Confluence 6 通过 SSL 或 HTTPS 运行 - 为 HTTPS 修改你的 Confluence 基础 URL
  11. vim常用指令整理小结
  12. Js批量下载花瓣网及堆糖网专辑图片
  13. Java - 32 Java 多线程编程
  14. 『jQuery』.html(),.text()和.val()的使用
  15. 30、hashCode方法
  16. 有间距的表格布局 table布局
  17. Windows Server 2012部署第一台域控
  18. jquery 上传图片自由截取
  19. java里面的public static void main(String[] args)
  20. g++中宏NULL究竟是什么?

热门文章

  1. 【转】http 缓存
  2. 数字图像处理实验(12):PROJECT 05-03,Periodic Noise Reduction Using a Notch Filter 标签: 图像处理MATLAB 2017-0
  3. poj1722 SUBTRACT
  4. CLR 显示实现事件 EventSet内部管理一个字典
  5. codefirst 最新策略
  6. 专题1-MMU-lesson2-深入剖析地址转化
  7. 运行monitor提示需要安装旧JAVA SE 6运行环境
  8. 在UIWebView中添加自定义编辑菜单
  9. C# worksheet设置Excel样式
  10. centos7下git的安装和配置