HDU 3435 A new Graph Game(最小费用流:有向环权值最小覆盖)
2024-08-25 21:44:05
http://acm.hdu.edu.cn/showproblem.php?pid=3435
题意:
有n个点和m条边,你可以删去任意条边,使得所有点在一个哈密顿路径上,路径的权值得最小。
思路:
费用流,注意判断重边,否则会超时。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL; const int maxn=+;
const int INF=0x3f3f3f3f; int map[maxn][maxn]; struct Edge
{
int from, to, cap, flow, cost;
Edge(int u, int v, int c, int f, int w) :from(u), to(v), cap(c), flow(f), cost(w) {}
}; struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn]; void init(int n)
{
this->n = n;
for (int i = ; i<n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap, int cost)
{
edges.push_back(Edge(from, to, cap, , cost));
edges.push_back(Edge(to, from, , , -cost));
m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
} bool BellmanFord(int s, int t, int &flow, LL & cost)
{
for (int i = ; i<n; i++) d[i] = INF;
memset(inq, , sizeof(inq));
d[s] = ; inq[s] = ; p[s] = ; a[s] = INF; queue<int> Q;
Q.push(s);
while (!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = ;
for (int i = ; i<G[u].size(); i++){
Edge& e = edges[G[u][i]];
if (e.cap>e.flow && d[e.to]>d[u] + e.cost){
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to]) { Q.push(e.to); inq[e.to] = ; }
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += (LL)d[t] * (LL)a[t];
for (int u = t; u != s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u] ^ ].flow -= a[t]; }
return true;
} int MincostMaxdflow(int s, int t, LL & cost)
{
int flow = ; cost = ;
while (BellmanFord(s, t, flow, cost) );
return flow;
}
}t; int n,m; int main()
{
//freopen("D:\\input.txt", "r", stdin);
int T;
int kase=;
scanf("%d",&T);
int u,v,d;
while(T--)
{
memset(map,,sizeof(map));
scanf("%d%d",&n,&m);
int src=,dst=*n+;
t.init(dst+);
for(int i=;i<=n;i++)
{
t.AddEdge(src,i,,);
t.AddEdge(i+n,dst,,);
}
for(int i=;i<m;i++)
{
scanf("%d%d%d",&u,&v,&d);
if(map[u][v]== || map[u][v]>d)
{
t.AddEdge(u,v+n,,d);
t.AddEdge(v,u+n,,d);
map[u][v]=map[v][u]=d;
}
}
long long cost;
int flow=t.MincostMaxdflow(src,dst,cost);
printf("Case %d: ",++kase);
if(flow==n) printf("%d\n",cost);
else printf("NO\n");
}
return ;
}
最新文章
- 【JUC】JDK1.8源码分析之CountDownLatch(五)
- ASP.NET Core 运行原理剖析2:Startup 和 Middleware(中间件)
- Android6.0动态申请权限
- SQL创建字段信息(表值函数)
- TCP心跳 | TCP keepAlive(转)
- BZOJ4605 : 崂山白花蛇草水
- 转帖-[教程] Win7精简教程(简易中度)2016年8月-0day
- 利用破解dll来获取到一个软件的注册码
- eclipse中基于maven构建的web项目pom.xml中指定的jar包无法发布到tomcat中
- 图书封面制作-ps图片处理使用教程
- wordpress网站被挂马以及防御方法
- Face The Right Way
- shell脚本采用crontab定时备份数据库日志
- 【死磕Java并发】-----深入分析volatile的实现原理
- vertical-align 与 line-height 傻傻分不清??
- K:java中正则表达式的使用说明及其举例
- java持有对象-集合类
- 【倍增】T-shirt @2018acm徐州邀请赛 I
- Xcodebuild ipa shell
- Axure RP Extension for Chrome修复
热门文章
- navigater导航
- 【BZOJ3677】[Apio2014]连珠线 换根DP
- mysql如何用sql增加字段和注释?
- centos7修改网卡名、密码重置
- WebConfig配置详解大全
- Code Forces 18D Seller Bob(简单DP)
- In ZeroDB, the client is responsible for the database logic. Data encryption, decryption, and compression also happen client side. Therefore, the server never has any knowledge about the data, its str
- IntelliJ IDEA 插件
- 以太坊geth主网全节点部署
- Scala的类与类型