hdu 1853 Cyclic Tour 最小费用最大流
2024-10-08 17:17:41
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1853
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?
题意描述:n个城市里有m条单向路径,每条路径上有一个权值,每个城市都属于且仅属于某一个环,Tom计划环游这n个城市,并且每个城市都只能经过一次。问最后环游了n个城市后最小的权值和是多少。
算法分析:费用流的常见模型,对于初学费用流的我来说,还是挺新鲜的,也参考了其他ACMer的博客。
首先提取出模型:给定一个有向图,要求用若干个环覆盖整个图,并且覆盖的这些环的权值和最小。
建模:源点from和汇点to,拆点 i 为 i 和 i+n。 from->i(w为1,cost为0)(w为1是因为每个城市只能游历一次),i+n->to(w为1,cost为0),对于u->v,连接u->v+n(w为1,cost为路径上的权值)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int maxn=+;
const int M = +; int n,m,from,to;
struct node
{
int v,flow,cost;
int next;
}edge[M*];
int head[maxn],edgenum;
int dis[maxn],pre[maxn],pid[maxn],vis[maxn];
int Maxflow; void add(int u,int v,int flow,int cost)
{
edge[edgenum].v=v ;edge[edgenum].flow=flow ;
edge[edgenum].cost=cost ;edge[edgenum].next=head[u];
head[u]=edgenum++; edge[edgenum].v=u ;edge[edgenum].flow=;
edge[edgenum].cost=-cost ;edge[edgenum].next=head[v];
head[v]=edgenum++;
} int spfa()
{
for (int i= ;i<=to ;i++) dis[i]=inf;
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(from);
dis[from]=;
vis[from]=;
while (!Q.empty())
{
int u=Q.front() ;Q.pop() ;
vis[u]=;
for (int i=head[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].v;
if (edge[i].flow> && dis[v]>dis[u]+edge[i].cost)
{
dis[v]=dis[u]+edge[i].cost;
pre[v]=u;
pid[v]=i;
if (!vis[v])
{
vis[v]=;
Q.push(v);
}
}
}
}
return dis[to];
} int mincost()
{
int ans=,maxflow=;
int aug=;
while ()
{
aug=inf;
int tmp=spfa();
if (tmp==inf) break;
for (int i=to ;i!=from ;i=pre[i])
{
if (edge[pid[i] ].flow<aug)
aug=edge[pid[i] ].flow;
}
for (int i=to ;i!=from ;i=pre[i])
{
edge[pid[i] ].flow -= aug;
edge[pid[i]^ ].flow += aug;
}
maxflow += aug;
ans += tmp*aug;
}
Maxflow=maxflow;
return ans;
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-,sizeof(head));
edgenum=;
int a,b,c;
from=*n+;
to=from+;
Maxflow=;
for (int i= ;i<m ;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b+n,,c);
}
for (int i= ;i<=n ;i++)
{
add(from,i,,);
add(i+n,to,,);
}
int ans=mincost();
printf("%d\n",Maxflow==n ? ans : -);
}
return ;
}
最新文章
- C++开始前篇,深入编译链接(补充2)
- 一份关于Swift语言学习资源的整理文件
- 基于bootstrap + php +ajax datatable 插件的使用
- Eclipse 4.2 (Juno) &#39;Cannot create a server using the selected type&#39; in Tomcat 7 - Stack Overflow.html
- Aspect Oriented Programming using Interceptors within Castle Windsor and ABP Framework AOP
- Windows下安装node
- MySQL auto-extending data file
- MATLAB画ROC曲线,及计算AUC值
- lintcode:最大间隔
- PHP中刷新输出缓冲,立即输出数据
- dom4j 笔记【转】
- E - Number Sequence(第二季水)
- Spark on Mesos: 搭建Mesos的一些问题
- codeforces 598B Queries on a String
- jQuery中$.get、$.post、$.getJSON和$.ajax的用法
- H5 Canvas vs. SVG
- windows 中查找占用某个端口的进程并杀死的命令
- java jvm和android DVM区别
- 常见的CSS代码无效问题
- 基于Vue.js的uni-app前端框架结合.net core开发跨平台project