本文主要是介绍zoj 3792 Romantic Value（最小割下边数最小），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5300
大致题意：给出一个无向图，以及起点与终点。要删除一些边使得起点与终点不连通，在删掉边的权值之和最小的情况下要求删除的边数尽量少。求出一个比值：剩余边数权值和/删除的边数。
思路：删除边的权值之和最小显然是求最小割即最大流。但同时要求删除边数最少，解决方法是把边数也加到权值上去，一起求最大流，因为边数最多是1000,即每条边的边权置为 w*10000+1，1代表这一条边。然后求最小割，同时也把最小边数求了出来。若求得的最小割是ans，那么删除的边数为ans%10000,最小割是ans/10000。
#include <stdio.h>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 55;
const int maxm = 1010;struct node
{int v,w,next,re;
}edge[4*maxm];int n,m,s,t;
int cnt,head[maxn];
int dis[maxn],vis[maxn];
queue <int> que;void init()
{cnt = 0;memset(head,-1,sizeof(head));
}void add(int u, int v, int w)
{edge[cnt] = ((struct node){v,w,head[u],cnt+1});head[u] = cnt++;edge[cnt] = ((struct node){u,0,head[v],cnt-1});head[v] = cnt++;
}bool bfs()
{memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));while(!que.empty()) que.pop();dis[s] = 0;vis[s] = 1;que.push(s);while(!que.empty()){int u = que.front();que.pop();for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!vis[v] && edge[i].w){vis[v] = 1;que.push(v);dis[v] = dis[u] + 1;}}}if(dis[t] == 0)return false;return true;
}int dfs(int u, int delta)
{if(u == t)return delta;int ret = 0,tmp;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(edge[i].w && dis[v] == dis[u] + 1 && (tmp = dfs(v,min(delta,edge[i].w)))){edge[i].w -= tmp;edge[edge[i].re].w += tmp;return tmp;}}if(!ret)dis[u] = -1;return ret;
}int Dinic()
{int ans = 0,res;while(bfs()){while(res = dfs(s,INF))ans += res;}return ans;
}int main()
{int test;int u,v,w;int sum;scanf("%d",&test);while(test--){scanf("%d %d %d %d",&n,&m,&s,&t);init();sum = 0;for(int i = 1; i <= m; i++){scanf("%d %d %d",&u,&v,&w);add(u,v,w*10000+1);add(v,u,w*10000+1);sum += w;}int ans = Dinic();if(ans == 0){printf("Inf\n");continue;}int a = sum - ans/10000;int b = ans%10000;printf("%.2lf\n",(double)a/b);}return 0;
}
这篇关于zoj 3792 Romantic Value（最小割下边数最小）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
