2018-2019 ICPC南京赛区I.Magic Potion（网络流-最大流）
发布时间
阅读量：
阅读量
题意
设定有n名英雄与m只怪物。对于每个第i名英雄来说，在他可击败的属于mi集合内的怪物中必须能够击败至少一只。若拥有k瓶 magical potion，则每瓶 potion可以让任意一名玩家对抗至少一只新增的怪物的能力得到提升。请问如此情况下最多能消灭多少只怪物？
题解
计算最大流量时，在图中将m个怪物重新编号至2+n至n+m的位置，并将n个勇士重新编排至2至n的位置。设定源点编号为0，并确定汇点编号h=n+m+2。在图中使勇士与怪物之间建立连接，并将每条边的流量上限设为1。将源点分别与所有勇士建立连接，并使每条边的流量上限设为1。引入一个虚拟节点并将其作为中间枢纽：将源点与该虚拟节点相连，并使这条边的流量上限设为k；然后使虚拟节点分别与所有勇士建立连接，并使每条边的流量上限设为1。最后，在图中让每一个怪物均与其对应的汇点建立连接，并使每条边的流量上限设为1（假设每个怪物最多被消灭一次）。
ac代码：
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define M_PI 3.14159265358979323846
int M[1005][1005],pre[1005],flow[1005];
int bfs(int s,int e)
{
queue<int>q;
q.push(s);
memset(pre,-1,sizeof(pre));
flow[s]=0x3f3f3f3f;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=0;v<=e;v++)
{
if(M[u][v]&&pre[v]==-1)
{
pre[v]=u;
flow[v]=min(flow[u],M[u][v]);
q.push(v);
}
}
}
if(pre[e]==-1) return -1;//找不到增广路
else return flow[e];
}
int maxflow(int s,int e)
{
int delt,res=0;
while((delt=bfs(s,e))!=-1)
{
int k=e,last=pre[k];
while(k!=s)
{
M[last][k]-=delt;
M[k][last]+=delt;
k=pre[k];
last=pre[k];
}
res+=delt;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
int h=n+m+2;
M[0][1]=k;//源点与虚拟节点相连，流量设置为k
for(int i=1;i<=n;i++) M[0][i+1]=1,M[1][i+1]=1;//源点连向所有勇士，流量设为1，虚拟节点连向所有的勇士，流量为1
for(int i=1;i<=m;i++) M[n+i+1][h]=1;//所有怪兽节点连向汇点，流量设置为1
for(int i=1;i<=n;i++)
{
int t,x;
cin>>t;
for(int j=0;j<t;j++)
{
cin>>x;
M[i+1][x+n+1]=1;
}
}
cout<<maxflow(0,h)<<endl;
return 0;
}
AI写代码全部评论 (0)
还没有任何评论哟~