网络流求最小割,另开源点汇点。
对于n个点,如果站力消耗大于0,则源点连条消耗值为权的边过去,反之这个点连条消耗值的绝对值为权的边到汇点,如果攻占b之后才可以攻占a,那么就连条a->b 权值为inf。然后结果就是所有正值之和减去最大流
#include<cstdio>
#include<cstring>
int n,head[600],dis[600],gap[600],s,t,m,sum,cnt;
const int inf=1<<30;
struct EDGE
{
int to,f,nxt;
}edge[600000];
int min(int a,int b)
{
return a<b?a:b;
}
void init()
{
sum=cnt=0;
memset(gap,0,sizeof(gap));
m......
阅读全文