HDU 2435 There is a war（修改或添加一條邊的最小割 ）經典
There is a war
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 952 Accepted Submission(s): 269
Problem Description There is a sea.
There are N islands in the sea.
There are some directional bridges connecting these islands.
There is a country called Country One located in Island 1.
There is another country called Country Another located in Island N.
There is a war against Country Another, which launched by Country One.
There is a strategy which can help Country Another to defend this war by destroying the bridges for the purpose of making Island 1 and Island n disconnected.
There are some different destroying costs of the bridges.
There is a prophet in Country Another who is clever enough to find the minimum total destroying costs to achieve the strategy.
There is an architecture in Country One who is capable enough to rebuild a bridge to make it unbeatable or build a new invincible directional bridge between any two countries from the subset of island 2 to island n-1.
There is not enough time for Country One, so it can only build one new bridge, or rebuild one existing bridge before the Country Another starts destroying, or do nothing if happy.
There is a problem: Country One wants to maximize the minimum total destroying costs Country Another needed to achieve the strategy by making the best choice. Then what’s the maximum possible result?
Input There are multiple cases in this problem.
There is a line with an integer telling you the number of cases at the beginning.
The are two numbers in the first line of every case, N(4<=N<=100) and M(0<=M<=n*(n-1)/2), indicating the number of islands and the number of bridges.
There are M lines following, each one of which contains three integers a, b and c, with 1<=a, b<=N and 1<=c<=10000, meaning that there is a directional bridge from a to b with c being the destroying cost.
There are no two lines containing the same a and b.
Output There is one line with one integer for each test case, telling the maximun possible result.
Sample Input
4
4 0
4 2
1 2 2
3 4 2
4 3
1 2 1
2 3 1
3 4 10
4 3
1 2 5
2 3 2
3 4 3
Sample Output
0
2
1
3
Source 2008 Asia Chengdu Regional Contest Online 題意：給一個有向圖，拆掉的邊的代價為邊權，現在1 要到n，n 試圖阻止1到達，至少花多大代價，條件是1 可以在任意兩點（不含1和n）只能修改或新增一條邊（此邊不可被拆），求n要花費的最小代價。
解題：如果沒有條件，那麼就是一道最簡單的最小割，但現在加一個條件 修改或新增一條邊。首先求出最初的最小割，就會把n個點分成兩部分：與匯點n相連，與源點相連。我們先用一個bfs標記與源點相連的那些點，那麼沒有被標記的點可能就是與匯點相連。 我們來分析一下：如果 修改或新增一條邊的兩個點要麼兩點都是與源點相連的點，要麼都是與匯點相連，那麼最小割是不會改變的，所以修改或新增的邊的兩個點（u,v）只能是u屬於與源點相連，v與匯點相連，邊權改成INF，這樣才有可能使最小割變大。如果是修改存在的邊，求完最小割要記得改回原來的值，如果是新增的邊，那麼要使邊權變為0。
#include
#include
#include
#include
using namespace std;
#define captype int
const int MAXN = 110; //點的總數
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 id[MAXN][MAXN],vist[MAXN];
void bfs()
{
queueq;
int u,v;
memset(vist,0,sizeof(vist));
vist[1]=1;
q.push(1);
while(!q.empty()) {
u=q.front(); q.pop();
for(int i=head[u]; i!=-1; i=edg[i].next ){
v=edg[i].to;
if(!vist[v]&&edg[i].cap-edg[i].flow>0)
vist[v]=1,q.push(v);
}
}
}
int main()
{
int T,n,m,u,v,c;
scanf(%d,&T);
while(T--)
{
scanf(%d%d,&n,&m);
init();
memset(id,-1,sizeof(id));
while(m--)
{
scanf(%d%d%d,&u,&v,&c);
id[u][v]=eid;
addEdg(u,v,c);
}
int ans=maxFlow_sap(1,n,n);
bfs();
for(int i=2; ians)ans=tans;
}
printf(%d
,ans);
}
}
