Harry Potter and the Forbidden ForestTime Limit: 5000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1791Accepted Submission(s): 596
Problem Description
Harry Potter notices some Death Eaters try to slip into Castle. The Death Eaters hide in the most depths of Forbidden Forest. Harry need stop them as soon as.
The Forbidden Forest is mysterious. It consists of N nodes numbered from 0 to N-1. All of Death Eaters stay in the node numbered 0. The position of Castle is node n-1. The nodes connected by some roads. Harry need block some roads by magic and he want to minimize the cost. But it’s not enough, Harry want to know how many roads are blocked at least.
Input
Input consists of several test cases.The first line is number of test case.Each test case, the first line contains two integers n, m, which means the number of nodes and edges of the graph. Each node is numbered 0 to n-1.Following m lines contains information about edges. Each line has four integers u, v, c, d. The first two integers mean two endpoints of the edges. The third one is cost of block the edge. The fourth one means directed (d = 0) or undirected (d = 1).Technical Specification1. 2 <= n <= 10002. 0 <= m <= 1000003. 0 <= u, v <= n-14. 0 < c <= 10000005. 0 <= d <= 1
Output
For each test case:Output the case number and the answer of how many roads are blocked at least.
Sample Input
34 50 1 3 00 2 1 01 2 1 11 3 1 12 3 3 16 70 1 1 00 2 1 00 3 1 01 4 1 02 4 1 03 5 1 04 5 2 03 60 1 1 00 1 2 01 1 1 11 2 1 01 2 1 02 1 1 1
Sample Output
Case 1: 3Case 2: 2Case 3: 2
Author
aMR @ WHU
Source
2011 Multi-University Training Contest 15 – Host by WHU
思路：我们知道最小割是不唯一的，这里要我们求割边最少的最小割，比较好做法有：
第一种：建边的时候每条边权 w = w * (E + 1) + 1;这样得到最大流 maxflow / (E + 1)，最少割边数 maxflow % (E + 1)
道理很简单，如果原先两类割边都是最小割，那么求出的最大流相等但边权变换后只有边数小的才是最小割了
乘（E+1）是为了保证边数叠加后依然是余数，不至于影响求最小割的结果
第二种：
建图，得到最大流后，图中边若满流，说明该边是最小割上的边
再建图，原则：满流的边改为容量为 1 的边，未满流的边改为容量 INF 的边（所改的边都是正向边），然后最大流即答案
/*最大流：SAP算法，与ISAP的差别就是不用预处理*/#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>using namespace std;#define captype intconst int MAXN = 1010; //点的总数const int MAXM = 400010; //边的总数const int INF = 1<<30;struct EDG{int to,next;captype cap,flow;} edg[MAXM];int eid,head[MAXN];int gap[MAXN]; //每种距离(或可认为是高度)点的个数int dis[MAXN]; //每个点到终点eNode 的最短距离int cur[MAXN]; //cur[u] 表示从u点出发可流经 cur[u] 号边int pre[MAXN];void init(){eid=0;memset(head,-1,sizeof(head));}//有向边 三个参数，无向边4个参数void addEdg(int u,int v,captype c,captype rc=0){edg[eid].to=v; edg[eid].next=head[u];edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v];edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;}captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));memcpy(cur,head,sizeof(head));pre[sNode] = -1;gap[0]=n;captype ans=0; //最大流int u=sNode;while(dis[sNode]<n){ //判断从sNode点有没有流向下一个相邻的点if(u==eNode){ //找到一条可增流的路captype Min=INF ;int inser;for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]) //从这条可增流的路找到最多可增的流量Minif(Min>edg[i].cap-edg[i].flow){Min=edg[i].cap-edg[i].flow;inser=i;}for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){edg[i].flow+=Min;edg[i^1].flow-=Min; //可回流的边的流量}ans+=Min;u=edg[inser^1].to;continue;}bool flag = false; //判断能否从u点出发可往相邻点流int v;for(int i=cur[u]; i!=-1; i=edg[i].next){v=edg[i].to;if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}//如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1int Mind= n;for(int i=head[u]; i!=-1; i=edg[i].next)if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){Mind=dis[edg[i].to];cur[u]=i;}gap[dis[u]]–;if(gap[dis[u]]==0) return ans; //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径//因为汇点到当前点的距离只有一种，，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1gap[dis[u]]++;if(u!=sNode) u=edg[pre[u]^1].to; //退一条边}return ans;}int main(){int T,_cas=0,n,m,u,v,c,d;scanf("%d",&T);while(T–){init();scanf("%d%d",&n,&m);int vs=0,vt=n-1;for(int i=0; i<m; i++){scanf("%d%d%d%d",&u,&v,&c,&d);addEdg(u,v,c);if(d)addEdg(v,u,c);}maxFlow_sap(vs , vt , n);for(int i=0; i<eid; i++)if(edg[i].cap==edg[i].flow&&edg[i].cap)edg[i].flow=0,edg[i].cap=1;else if(edg[i].cap)edg[i].flow=0,edg[i].cap=INF;int ans=maxFlow_sap(vs , vt , n);printf("Case %d: %d\n",++_cas,ans);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
去追寻那飞翔的翅膀。落叶随风淡定了它漂泊的方向。
