正文
HDU 3435 A new Graph Game(最小费用最大流)&HDU 3488
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
A new Graph Game
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1849 Accepted Submission(s): 802
Problem Description
An undirected graph is a graph in which the nodes are connected by undirected arcs. An undirected arc is an edge that has no arrow. Both ends of an undirected arc are equivalent--there is no head or tail. Therefore, we represent an
edge in an undirected graph as a set rather than an ordered pair.
Now given an undirected graph, you could delete any number of edges as you wish. Then you will get one or more connected sub graph from the original one (Any of them should have more than one vertex).
You goal is to make all the connected sub graphs exist the Hamiltonian circuit after the delete operation. What’s more, you want to know the minimum sum of all the weight of the edges on the “Hamiltonian circuit” of all the connected sub graphs (Only one “Hamiltonian
circuit” will be calculated in one connected sub graph! That is to say if there exist more than one “Hamiltonian circuit” in one connected sub graph, you could only choose the one in which the sum of weight of these edges is minimum).
For example, we may get two possible sums:
(1) 7 + 10 + 5 = 22
(2) 7 + 10 + 2 = 19
(There are two “Hamiltonian circuit” in this graph!)
edge in an undirected graph as a set rather than an ordered pair.
Now given an undirected graph, you could delete any number of edges as you wish. Then you will get one or more connected sub graph from the original one (Any of them should have more than one vertex).
You goal is to make all the connected sub graphs exist the Hamiltonian circuit after the delete operation. What’s more, you want to know the minimum sum of all the weight of the edges on the “Hamiltonian circuit” of all the connected sub graphs (Only one “Hamiltonian
circuit” will be calculated in one connected sub graph! That is to say if there exist more than one “Hamiltonian circuit” in one connected sub graph, you could only choose the one in which the sum of weight of these edges is minimum).
For example, we may get two possible sums:
(1) 7 + 10 + 5 = 22
(2) 7 + 10 + 2 = 19
(There are two “Hamiltonian circuit” in this graph!)
Input
In the first line there is an integer T, indicates the number of test cases. (T <= 20)
In each case, the first line contains two integers n and m, indicates the number of vertices and the number of edges. (1 <= n <=1000, 0 <= m <= 10000)
Then m lines, each line contains three integers a,b,c ,indicates that there is one edge between a and b, and the weight of it is c . (1 <= a,b <= n, a is not equal to b in any way, 1 <= c <= 10000)
In each case, the first line contains two integers n and m, indicates the number of vertices and the number of edges. (1 <= n <=1000, 0 <= m <= 10000)
Then m lines, each line contains three integers a,b,c ,indicates that there is one edge between a and b, and the weight of it is c . (1 <= a,b <= n, a is not equal to b in any way, 1 <= c <= 10000)
Output
Output “Case %d: “first where d is the case number counted from one. Then output “NO” if there is no way to get some connected sub graphs that any of them exists the Hamiltonian circuit after the delete operation. Otherwise, output
the minimum sum of weight you may get if you delete the edges in the optimal strategy.
the minimum sum of weight you may get if you delete the edges in the optimal strategy.
Sample Input
3 3 4
1 2 5
2 1 2
2 3 10
3 1 7 3 2
1 2 3
1 2 4 2 2
1 2 3
1 2 4
Sample Output
Case 1: 19
Case 2: NO
Case 3: 6HintIn Case 1:
You could delete edge between 1 and 2 whose weight is 5. In Case 2:
It’s impossible to get some connected sub graphs that any of them exists the Hamiltonian circuit after the delete operation.
Author
AekdyCoin
Source
2010 ACM-ICPC Multi-University Training Contest(1)——Host
by FZU
by FZU
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 10010;
const int MAXM = 100100;
const int INF = 1<<30;
struct EDG{
int to,next,cap,flow;
int cost; //每条边的单位价格
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //点0~(n-1) void init(){
eid=0;
memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++; edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++;
} bool inq[MAXN];
bool spfa(int sNode,int eNode,int n){
queue<int>q;
for(int i=0; i<n; i++){
inq[i]=false; cost[i]= INF;
}
cost[sNode]=0; inq[sNode]=1; pre[sNode]=-1;
q.push(sNode);
while(!q.empty()){
int u=q.front(); q.pop();
inq[u]=0;
for(int i=head[u]; i!=-1; i=edg[i].next){
int v=edg[i].to;
if(edg[i].cap-edg[i].flow>0 && cost[v]>cost[u]+edg[i].cost){ //在满足可增流的情况下。最小花费
cost[v] = cost[u]+edg[i].cost;
pre[v]=i; //记录路径上的边
if(!inq[v])
q.push(v),inq[v]=1;
}
}
}
return cost[eNode]!=INF; //推断有没有增广路
}
//反回的是最大流,最小花费为minCost
int minCost_maxFlow(int sNode,int eNode ,int& minCost,int n){
int ans=0;
while(spfa(sNode,eNode,n)){
ans++;
for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){
edg[i].flow+=1; edg[i^1].flow-=1;
minCost+=edg[i].cost;
}
}
return ans;
}
void scanf(int &ans){
char ch;
while(ch=getchar()){
if(ch>='0'&&ch<='9')
break;
}
ans=ch-'0';
while(ch=getchar()){
if(ch<'0'||ch>'9')
break;
ans=ans*10+ch-'0';
}
}
int mapt[1005][1005];
int main(){
int T,_case=0,n,m , u, v, d ;
scanf(T);
while(T--){
scanf(n); scanf(m);
init();
int s=0, t=2*n+1; for(int i=1; i<=n; i++){
addEdg(s , i , 1 , 0);
addEdg(i+n , t , 1 , 0);
for(int j=1; j<=n; j++)
mapt[i][j]=INF;
}
while(m--){
scanf(u); scanf(v); scanf(d);
if(mapt[u][v]>d)
mapt[u][v]=mapt[v][u]=d;
}
for( u=1; u<=n; u++)
for(v=1; v<=n; v++)
if(mapt[u][v]!=INF)
addEdg(u,v+n,1,mapt[u][v]); int mincost=0;
n-= minCost_maxFlow(s , t , mincost , t+1);
printf("Case %d: ",++_case);
if(n==0)
printf("%d\n",mincost);
else
printf("NO\n");
}
}
HDU 3435 A new Graph Game(最小费用最大流)&HDU 3488的更多相关文章
-
【进阶——最小费用最大流】hdu 1533 Going Home (费用流)Pacific Northwest 2004
题意: 给一个n*m的矩阵,其中由k个人和k个房子,给每个人匹配一个不同的房子,要求所有人走过的曼哈顿距离之和最短. 输入: 多组输入数据. 每组输入数据第一行是两个整型n, m,表示矩阵的长和宽. ...
-
hdu 2485 Destroying the bus stations 最小费用最大流
题意: 最少需要几个点才能使得有向图中1->n的距离大于k. 分析: 删除某一点的以后,与它相连的所有边都不存在了,相当于点的容量为1.但是在网络流中我们只能直接限制边的容量.所以需要拆点来完成 ...
-
hdu 2686&&hdu 3376(拆点+构图+最小费用最大流)
Matrix Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Subm ...
-
hdu 3488(KM算法||最小费用最大流)
Tour Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submis ...
-
hdu 2686 Matrix 最小费用最大流
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2686 Yifenfei very like play a number game in the n*n ...
-
hdu 1533 Going Home 最小费用最大流
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1533 On a grid map there are n little men and n house ...
-
hdu 4494 Teamwork 最小费用最大流
Teamwork Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4494 ...
-
HDU 5988.Coding Contest 最小费用最大流
Coding Contest Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)To ...
-
hdu 3667(拆边+最小费用最大流)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3667 思路:由于花费的计算方法是a*x*x,因此必须拆边,使得最小费用流模板可用,即变成a*x的形式. ...
-
hdu 3395(KM算法||最小费用最大流(第二种超级巧妙))
Special Fish Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tota ...
随机推荐
-
windowsclient开发--duilib显示html
今天与大家分享的就是duilib这个库中,怎样做到显示html的. 有些控件,如Text能够通过showhtml函数来设置是否显示html富文本. 加粗 {b}加粗{/b} 斜体 {i}斜体{/i} ...
-
Memcached--分布式缓存安装教程
Memcached的Windows版本在这里下载http://code.google.com/p/memcached/wiki/PlatformWindows(或http://memcachedpro ...
-
java.lang.NoClassDefFoundError: com.baidu.mapapi.BMapManager
解决方案:一.右击项目->properties->Java Build Path->Order and Export,在需要引用的包前面打勾.二.Project->Clean. ...
-
poj 2391 (Floyd+最大流+二分)
题意:有n块草地,一些奶牛在草地上吃草,草地间有m条路,一些草地上有避雨点,每个避雨点能容纳的奶牛是有限的,给出通过每条路的时间,问最少需要多少时间能让所有奶牛进入一个避雨点. 两个避雨点间可以相互到 ...
-
glassfish--服务搭建
集群配置: 1. DAS节点执行: 1)./asadmin start-domain domain1 2)./asadmin change-admin-password 3)./asadmin ena ...
-
Hotaru's problem(hdu5371+Manacher)多校7
Hotaru's problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) ...
-
1z0-052 q209_6
6: You executed this command to create a temporary table: SQL> CREATE GLOBAL TEMPORARY TABLE repo ...
-
webpack配置上线地址
webpack配置上线地址主要使用output配置项下的publicPath. webpack.config.js配置文件为: var htmlWebpackPlugin = require('htm ...
-
CSS实现水平垂直居中方式
1.定位 核心代码实现请看示例代码中的注释: <!DOCTYPE html> <html lang="zh"> <head> <meta ...
-
在jsp页面上打印错误堆栈
try{ .................... } catch(Exception e){ //定义一个流 ByteArrayOutputStream ostr = new ByteArrayOu ...
题意: 给一个n*m的矩阵,其中由k个人和k个房子,给每个人匹配一个不同的房子,要求所有人走过的曼哈顿距离之和最短. 输入: 多组输入数据. 每组输入数据第一行是两个整型n, m,表示矩阵的长和宽. ...
题意: 最少需要几个点才能使得有向图中1->n的距离大于k. 分析: 删除某一点的以后,与它相连的所有边都不存在了,相当于点的容量为1.但是在网络流中我们只能直接限制边的容量.所以需要拆点来完成 ...
Matrix Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Subm ...
Tour Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submis ...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2686 Yifenfei very like play a number game in the n*n ...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1533 On a grid map there are n little men and n house ...
Teamwork Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4494 ...
Coding Contest Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)To ...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3667 思路:由于花费的计算方法是a*x*x,因此必须拆边,使得最小费用流模板可用,即变成a*x的形式. ...
Special Fish Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tota ...
-
windowsclient开发--duilib显示html
今天与大家分享的就是duilib这个库中,怎样做到显示html的. 有些控件,如Text能够通过showhtml函数来设置是否显示html富文本. 加粗 {b}加粗{/b} 斜体 {i}斜体{/i} ...
-
Memcached--分布式缓存安装教程
Memcached的Windows版本在这里下载http://code.google.com/p/memcached/wiki/PlatformWindows(或http://memcachedpro ...
-
java.lang.NoClassDefFoundError: com.baidu.mapapi.BMapManager
解决方案:一.右击项目->properties->Java Build Path->Order and Export,在需要引用的包前面打勾.二.Project->Clean. ...
-
poj 2391 (Floyd+最大流+二分)
题意:有n块草地,一些奶牛在草地上吃草,草地间有m条路,一些草地上有避雨点,每个避雨点能容纳的奶牛是有限的,给出通过每条路的时间,问最少需要多少时间能让所有奶牛进入一个避雨点. 两个避雨点间可以相互到 ...
-
glassfish--服务搭建
集群配置: 1. DAS节点执行: 1)./asadmin start-domain domain1 2)./asadmin change-admin-password 3)./asadmin ena ...
-
Hotaru's problem(hdu5371+Manacher)多校7
Hotaru's problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) ...
-
1z0-052 q209_6
6: You executed this command to create a temporary table: SQL> CREATE GLOBAL TEMPORARY TABLE repo ...
-
webpack配置上线地址
webpack配置上线地址主要使用output配置项下的publicPath. webpack.config.js配置文件为: var htmlWebpackPlugin = require('htm ...
-
CSS实现水平垂直居中方式
1.定位 核心代码实现请看示例代码中的注释: <!DOCTYPE html> <html lang="zh"> <head> <meta ...
-
在jsp页面上打印错误堆栈
try{ .................... } catch(Exception e){ //定义一个流 ByteArrayOutputStream ostr = new ByteArrayOu ...