hdu 1853(拆点判环+费用流)
2024-09-27 05:47:42
Cyclic Tour
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 2257 Accepted Submission(s): 1148
Problem Description
There
are N cities in our country, and M one-way roads connecting them. Now
Little Tom wants to make several cyclic tours, which satisfy that, each
cycle contain at least two cities, and each city belongs to one cycle
exactly. Tom wants the total length of all the tours minimum, but he is
too lazy to calculate. Can you help him?
are N cities in our country, and M one-way roads connecting them. Now
Little Tom wants to make several cyclic tours, which satisfy that, each
cycle contain at least two cities, and each city belongs to one cycle
exactly. Tom wants the total length of all the tours minimum, but he is
too lazy to calculate. Can you help him?
Input
There are several test cases in the input. You should process to the end of file (EOF).
The
first line of each test case contains two integers N (N ≤ 100) and M,
indicating the number of cities and the number of roads. The M lines
followed, each of them contains three numbers A, B, and C, indicating
that there is a road from city A to city B, whose length is C. (1 ≤ A,B ≤
N, A ≠ B, 1 ≤ C ≤ 1000).
The
first line of each test case contains two integers N (N ≤ 100) and M,
indicating the number of cities and the number of roads. The M lines
followed, each of them contains three numbers A, B, and C, indicating
that there is a road from city A to city B, whose length is C. (1 ≤ A,B ≤
N, A ≠ B, 1 ≤ C ≤ 1000).
Output
Output one number for each test case, indicating the minimum length of all the tours. If there are no such tours, output -1.
Sample Input
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
6 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
6 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
Sample Output
42
-1
-1
Hint
In the first sample, there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42.
题意:n个城市,m条路线,现在要对这些城市进行规划,每个城市都要被规划进一个环里面,而且只能出现一次,现在问能否做到?如果能够做到,输出最小路径和.
题解:最小费用最大流+拆点,如果城市在环里面,那么这个点的出度,入度都为1,将一个人拆成 i ,i+n,那么我们就限制了当前的人只能够用一次,然后对i ,j+n 建立关系,跑一遍最小费用最大流即可。如果最大流<n,那么则是无解的.
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = ;
const int N = ;
const int M = ;
struct Edge{
int u,v,cap,cost,next;
}edge[M];
int head[N],tot,low[N],pre[N];
int total ;
bool vis[N];
void addEdge(int u,int v,int cap,int cost,int &k){
edge[k].u=u,edge[k].v=v,edge[k].cap = cap,edge[k].cost = cost,edge[k].next = head[u],head[u] = k++;
edge[k].u=v,edge[k].v=u,edge[k].cap = ,edge[k].cost = -cost,edge[k].next = head[v],head[v] = k++;
}
void init(){
memset(head,-,sizeof(head));
tot = ;
}
bool spfa(int s,int t,int n){
memset(vis,false,sizeof(vis));
for(int i=;i<=n;i++){
low[i] = (i==s)?:INF;
pre[i] = -;
}
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int k=head[u];k!=-;k=edge[k].next){
int v = edge[k].v;
if(edge[k].cap>&&low[v]>low[u]+edge[k].cost){
low[v] = low[u] + edge[k].cost;
pre[v] = k; ///v为终点对应的边
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t]==-) return false;
return true;
}
int MCMF(int s,int t,int n){
int mincost = ,minflow,flow=;
while(spfa(s,t,n))
{
minflow=INF+;
for(int i=pre[t];i!=-;i=pre[edge[i].u])
minflow=min(minflow,edge[i].cap);
flow+=minflow;
for(int i=pre[t];i!=-;i=pre[edge[i].u])
{
edge[i].cap-=minflow;
edge[i^].cap+=minflow;
}
mincost+=low[t]*minflow;
}
total=flow;
return mincost;
}
int n,m;
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
int src = ,des = *n+;
for(int i=;i<=n;i++){
addEdge(src,i,,,tot);
addEdge(i+n,des,,,tot);
}
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v+n,,w,tot);
}
int mincost = MCMF(src,des,*n+);
if(total!=n) printf("-1\n");
else printf("%d\n",mincost);
}
}
最新文章
- Alpha阶段第四次Scrum Meeting
- timus 1180. Stone Game 解题报告
- iOS软件版本更新思路
- java学习随笔--- 捣蛋vector
- java 发送 http 请求
- (转)java生成UUID通用唯一识别码 (Universally Unique Identifier)
- H2Engine游戏服务器设计之属性管理器
- unix时间戳转换成标准时间(c#)
- [BZOJ1861][ZJOI2006]书架
- [BJOI2006]狼抓兔子
- public、protected、default、private区别
- C# 特性(Attribute)之Serializable特性
- DelayQueue源码解析
- nginx 文档链接
- if语句的嵌套以及条件运算符和条件表达式(初学者)
- make distclean
- 【论文阅读】Learning Spatial Regularization with Image-level Supervisions for Multi-label Image Classification
- Android-LayoutAnimation
- bzoj2035: [2009国家集训队]数据读取问题
- C语言 常用的宏定义