洛谷P2763题解
2019-08-16 07:59:12来源:博客园 阅读 ()
洛谷P2763题解
吐槽一下:蜜汁UKE是什么玩意?!
题目分析:
观察题面,
对于给定的组卷要求,计算满足要求的组卷方案
,可以发现这是一道明显的有条件的二分图匹配问题,于是考虑建模。建一个超级源点,一个超级汇点;源点与试题相连,汇点与类型相连。
重点是类型的题数的建模。可以从感性来理解一下,其实这有一点限流的意思,每个类型只要求有这么多的题量,不能超出,于是考虑在类型与汇点相连的时候将容量设为类型的题数,在算最大流的时候将题量限制住,就能满足题面的要求了。(希望大家能明白我的意思 \(QwQ\) )
- 最后的图即为:超级源点与试题相连,容量为1;类型与对应的试题相连,容量为1;类型与超级汇点相连,容量为类型的题数。具体来说,超级源点 \(S\) 为节点 \(1\) ,试题为节点 \(2—n+1\),类型为节点 \(n+2—n+k+1\) 超级汇点 \(T\) 为节点 \(n+k+2\) 。
- 建模完成之后,考虑记录方案。
- 因为 \(Dinic\) 算法是通过 \(Xor\;1\) 来完成正向边与反向边的转变的,故正向边的 \(e[i].to\) 为路径终点,反向边的 \(e[i\;Xor\;1].to\) 为路径起点, 所以可以通过枚举每一条边来找到相应的节点。
- 又因为反向边的 \(e[i\;Xor\;1].v\) 的初始化为0,当 \(e[i\;Xor\;1].v\neq0\) 时,即代表这条边是最大流跑过的边,也相当于这条边被匹配了。
- 最后排除掉超级源点与超级汇点的情况。
如果 \(Dinic\) 跑一遍下来,ans(即最大流)依然为0,则本数据没有答案(即输出"No Solution!")。
code(带详细注释):
#include<bits/stdc++.h>
#define Maxn 4010
#define Maxm 10010
#define int long long
using namespace std;
int k,n;
inline void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int S,T;
int ans=0,dep[Maxn];
struct edge
{
int to,next,v;
}e[Maxm<<1];//一定注意要开两倍空间(正反两条边)
int head[Maxn],ei=1;//一定注意这里的ei为奇数
void add(int x,int y,int v)
{
ei++;
e[ei].to=y;
e[ei].v=v;
e[ei].next=head[x];
head[x]=ei;
}
int bfs()
{
queue<int>qu;
memset(dep,0,sizeof(dep));
dep[S]=1;
qu.push(S);
while(!qu.empty())
{
int fr=qu.front();
qu.pop();
for(int i=head[fr];i;i=e[i].next)
{
int to=e[i].to;
if(dep[to]!=0||e[i].v==0) continue;
qu.push(to);
dep[to]=dep[fr]+1;
}
}
return dep[T]!=0;
}
int dfs(int from,int maxflow)
{
if(from==T) return maxflow;
int flow=0;
for(int i=head[from];i;i=e[i].next)
{
int to=e[i].to;
if(dep[to]!=dep[from]+1||e[i].v==0) continue;
int rst=dfs(to,min(maxflow-flow,e[i].v));
if(rst==0) dep[to]=0;
e[i].v-=rst;
e[i^1].v+=rst;
flow+=rst;
if(flow==maxflow) break;
}
return flow;
}
void dinic()
{
while(bfs())
{
ans+=dfs(S,LLONG_MAX);
}
}
signed main()
{
read(k),read(n);
S=1,T=k+n+2;//超级源点与超级汇点
for(int i=1;i<=n;i++)
{
add(S,i+1,1);
add(i+1,S,0);
//超级源点与试题相连,容量为1
}
for(int i=1,x;i<=k;i++)
{
read(x);
add(i+n+1,T,x);
add(T,i+n+1,0);
//类型与超级汇点相连,容量为类型的题数
}
for(int i=1,p;i<=n;i++)
{
read(p);
for(int j=1,x;j<=p;j++)
{
read(x);
add(i+1,x+n+1,1);
add(x+n+1,i+1,0);
//类型与对应的试题相连,容量为1
}
}
dinic();//跑dinic
if(ans==0)//没有答案
{
puts("No Solution!");
return 0;
}
for(int num=1;num<=k;num++)//枚举所有类型
{
printf("%lld:",num);
for(int i=2;i<=ei;i+=2)//枚举每一条边来找到相应的节点
{
if(e[i].to!=S&&e[i].to!=T&&e[i^1].to!=S&&e[i^1].to!=T)//排除掉超级源点与超级汇点的情况
{
if(e[i^1].v!=0)//这条边已经被匹配了
{
if(e[i].to-n-1==num)//判断是否为当前类型
{
printf("%lld ",e[i^1].to-1);
}
}
}
}
printf("\n");
}
return 0;
}
网络流注意事项:
- 网络流关键在于建模,精髓也在建模。像本题一样的二分图匹配问题可采取我使用的建模方式:最大匹配=最大流。
- 前向星的计数器初始化时,一定要为奇数。因为第n条边为正向边,第n+1条边为反向边,要实现 \(e[i]\) 为正向边,\(e[i\;Xor\;1]\) 为反向边,就要保证正向边的i为奇数,即计数器要初始化为奇数。
- 前向星边数一定要开两倍空间,因为正向边一条,反向边一条。
原文链接:https://www.cnblogs.com/nth-element/p/11313897.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- 洛谷P1907口算练习题 2020-03-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash