ZOJ3792_Romantic Value(網絡流/最小割=最大流/找割邊)
解題報告
題目傳送門
題意：
給出一個無向圖，以及起點與終點。要刪除一些邊使得起點與終點不連通，在刪掉邊的權值之和最小的情況下要求刪除的邊數盡量少。
求出一個比值：剩余邊數權值和/刪除的邊數。
思路：
明顯的讓起點終點達不到就是一個最小割，用最大流可以求出。
但是求割邊邊數就不會了，沒做過最小割的求割邊問題。
割邊一定是殘留網絡中零流的邊，但零流不一定是割邊。
飛神的想法很奇特。鏈接傳送
可以把殘留網絡的零流的邊設成容量為1，其他設成無窮，再求一次最大流。最後流量一定等於割邊邊數
另外：
還有一種求割邊的辦法。
因為每次我們求出來最大流都是割邊的流量，那麼，我們可以把原先邊的容量×10000+1，那麼求出來的最大流/10000不會影響原先的答案，而最大流%10000則是割邊的數目。orz，，，，，，
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
struct node {
int v,w,next;
} edge[500000];
int head[5000],cnt,n,m,l[5000],s,t,_hash[5000];
void add(int u,int v,int w) {
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].w=0;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int bfs() {
queueQ;
Q.push(s);
memset(l,-1,sizeof(l));
l[s]=0;
while(!Q.empty()) {
int u=Q.front();
Q.pop();
for(int i=head[u]; i!=-1; i=edge[i].next) {
int v=edge[i].v;
if(l[v]==-1&&edge[i].w) {
l[v]=l[u]+1;
Q.push(v);
}
}
}
return l[t]>0;
}
int dfs(int x,int f) {
if(x==t)return f;
int a;
for(int i=head[x]; i!=-1; i=edge[i].next) {
int v=edge[i].v;
if(edge[i].w&&l[v]==l[x]+1&&(a=dfs(v,min(edge[i].w,f)))) {
edge[i].w-=a;
edge[i^1].w+=a;
return a;
}
}
l[x]=-1;
return 0;
}
int main() {
int i,j,u,v,w,k=1,T,q,p;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d%d",&n,&m,&p,&q);
memset(head,-1,sizeof(head));
cnt=0;
s=p;
t=q;
int sum=0;
for(i=1; i<=m; i++) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
sum+=w;
}
if(!bfs()) {
printf("Inf\n");
continue;
}
int ans=0,a;
while(bfs())
while(a=dfs(s,inf))
ans+=a;
for(i=0; i
Romantic Value
Time Limit: 2 Seconds Memory Limit: 65536 KB
Farmer John is a diligent man. He spent a lot of time building roads between his farms. From his point of view, every road is romantic because the scenery along it is very harmonious
and beautiful. Recently, John is immersed in poetry, he wants stay alone and enjoy the wonderful words. But his little brother always disturbs him. This night, fortunately, his little brother does not stay the same farm with him. So, he wants to destroy some
roads to keep himself quiet for a few days(then no route exist between John and his brother). Of course, John love his romantic roads, so he want to separate him and his brother with least romantic cost.
There are N farms(numbered from 1 to N) and M undirected roads each with a romantic value c(indicate how much Farmer John loves it). Now John stays in farm p and his little brother stay
in farm q. John wants to first minimize the romantic value lost, then to destroy as few roads as possible. Help him to calculate the ratio of [sum of the remainder roads' value]/[the amount of removed roads](not necessary to maximisation this ratio)
when he achieves his goal.
Input
The first line is a single integer T, indicate the number of testcases. Then follows T testcase. For each testcase, the first line contains four integers N M p q(you can assume p and
q are unequal), then following M lines each contains three integer a b c which means there is an undirected road between farm a and farm b with romantic value c. (2<=N<=50, 0<=M<=1000, 1<=c<1000, 1<=p,q<=N)
Output
For each test case, print the ratio in a single line(keep two decimal places). If p and q exist no route at the start, then output "Inf".
Sample Input
1
4 5 1 4
1 2 1
1 3 1
2 4 2
3 4 2
2 3 1
Sample Output
2.50
