HDU 3987 Harry Potter and the Forbidden Forest（最小割中的最少割邊）經典
Harry Potter and the Forbidden Forest
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1791 Accepted 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 Specification
1. 2 <= n <= 1000
2. 0 <= m <= 100000
3. 0 <= u, v <= n-1
4. 0 < c <= 1000000
5. 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
3
4 5
0 1 3 0
0 2 1 0
1 2 1 1
1 3 1 1
2 3 3 1
6 7
0 1 1 0
0 2 1 0
0 3 1 0
1 4 1 0
2 4 1 0
3 5 1 0
4 5 2 0
3 6
0 1 1 0
0 1 2 0
1 1 1 1
1 2 1 0
1 2 1 0
2 1 1 1
Sample Output
Case 1: 3
Case 2: 2
Case 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
#include
#include
#include
using namespace std;
#define captype int
const 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]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的距離（也可認為是高度）為相鄰可流點的最小距離+1
int 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+1
gap[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
