本文主要是介绍hdu3987 Harry Potter and the Forbidden Forest 最小割割边最少，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给一个n个点构成的有向图，起点为0，终点为n-1。每条边有一个权值，删除一条边的代价为边权。问如何删除使得0和n-1不
联通且代价最小，在这种情况下至少要删除多少条边。
思路：首先保证代价最小，很容易想到是最小割，但是不知怎么保证割边最少= =看了大神博客。。恍然大悟。。模型真是见得
少。。我们设一个较大的值N(N>数据给的最大边数)，将边权变成w*N+1，那么最后求得的最大流对N取余自然就是最少割边。详见
代码：
/*********************************************************file name: hdu3987.cppauthor : kereocreate time: 2015年01月21日 星期三 15时55分52秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=1000000+50;
const int MAXN=1000+50;
const ll inf=1e17;
const double eps=1e-8;
const ll mod=1000000+1;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m,edge_cnt,top;
int head[MAXN],cur[MAXN],s[MAXN],que[MAXN],dep[MAXN],gap[MAXN];
struct Edge{int v,next;ll cap,flow;
}edge[N<<1];
void init(){edge_cnt=top=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,ll w){edge[edge_cnt].v=v; edge[edge_cnt].cap=w; edge[edge_cnt].flow=0;edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;edge[edge_cnt].v=u;edge[edge_cnt].cap=0; edge[edge_cnt].flow=0;edge[edge_cnt].next=head[v]; head[v]=edge_cnt++;
}
void bfs(int st,int ed){memset(gap,0,sizeof(gap));memset(dep,-1,sizeof(dep));int front=0,rear=0; que[rear++]=ed; gap[0]=1; dep[ed]=0;while(front!=rear){int u=que[front++];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(dep[v]!=-1)continue;que[rear++]=v; dep[v]=dep[u]+1; gap[dep[v]]++;}}
}
ll isap(int st,int ed){bfs(st,ed);memcpy(cur,head,sizeof(head));ll ans=0; int u=st;while(dep[st]<n){if(u == ed){ll Min=inf; int inser;for(int i=0;i<top;i++){if(edge[s[i]].cap-edge[s[i]].flow<Min){inser=i;Min=edge[s[i]].cap-edge[s[i]].flow;}}for(int i=0;i<top;i++)edge[s[i]].flow+=Min,edge[s[i]^1].flow-=Min;ans+=Min; top=inser;u=edge[s[top]^1].v;continue;}int flag=0,v;for(int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].v;if(edge[i].cap-edge[i].flow>0 && dep[v]+1 == dep[u]){flag=1; cur[u]=i;break;}}if(flag){s[top++]=cur[u]; u=v;continue;}int d=n;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(edge[i].cap-edge[i].flow>0 && dep[v]<d)cur[u]=i,d=dep[v];}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u]=d+1; gap[dep[u]]++;if(u!=st)u=edge[s[--top]^1].v;}return ans;
}
int main(){int T,kase=0;scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int u,v,w,d;scanf("%d%d%d%d",&u,&v,&w,&d);addedge(u,v,(ll)w*mod+1);if(d)addedge(v,u,(ll)w*mod+1);}printf("Case %d: %lld\n",++kase,isap(0,n-1)%mod);}return 0;
}这篇关于hdu3987 Harry Potter and the Forbidden Forest 最小割割边最少的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
