P2763 试题库问题
2024-08-26 03:34:56
显然的网络流,源点向所有题目连流量为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 ;
}
最新文章
- 【iCore3应用开发平台】发布 iCore3 应用开发平台出厂代码rev0.0.5
- x01.Lab.StoreApp: XP 停服,微软变脸
- EXTJS 资料 combo 点一次触发一次
- linux远程执行命令
- (转)PHP函数spl_autoload_register()用法和__autoload()介绍
- [HDU 1535]Invitation Cards[SPFA反向思维]
- DIV+CSS规范命名
- SWT的选择文件和文件夹的函数
- freemarker报错之十三
- Confluence 6 通过 SSL 或 HTTPS 运行 - 为 HTTPS 修改你的 Confluence 基础 URL
- vim常用指令整理小结
- Js批量下载花瓣网及堆糖网专辑图片
- Java - 32 Java 多线程编程
- 『jQuery』.html(),.text()和.val()的使用
- 30、hashCode方法
- 有间距的表格布局 table布局
- Windows Server 2012部署第一台域控
- jquery 上传图片自由截取
- java里面的public static void main(String[] args)
- g++中宏NULL究竟是什么?