HDU 3435 A new Graph Game(费用流)
http://acm.hdu.edu.cn/showproblem.php?pid=3435
题意:
给你一个N个节点M条边的无向图,要你求该图有1个或多个不相交有向环(哈密顿回路)构成时,所有这些有向环的最小权值.
分析:
本题之前用KM算法做过:
http://blog.csdn.net/u013480600/article/details/38780451
要注意,可以从本题的第3个用例的输出可以看出,本题的无向边,其实就是等效于两条方向相反的有向边.(如果本题的无向边==一条有向边,那么用例3无解).
所以对于本题来说无向图其实就是有向图的所有边必须添加两边(仅此而已),本题与之前所做HDU1853几乎一样的解法,详细可以参考HDU1853的分析:
http://blog.csdn.net/u013480600/article/details/39159407
建图如下(论证参考HDU1853):
源点s编号0,n个节点编号1到n和n+1到2*n, 汇点t编号2*n+1.
从源点s到第i个点有边 (s, i, 1, 0)
如果有无向边(i,j,w),那么有两条有向边 (i, j+n, 1, w) 和 (j, i+n, 1, w)
每个节点i到汇点t有边 (i+n, t, 1, 0)
最终我们求得最大流如果==n的话,最小费用就是解. 否则输出NO.
AC代码: C++3890MS, G++3671MS
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn = 2000+5;
struct Edge
{
int from,to,cap,flow,cost;
Edge(){}
Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int a[maxn];
int p[maxn];
void init(int n,int s,int t)
{
this->n=n, this->s=s, this->t=t;
edges.clear();
for(int i=0;i<n;++i) G[i].clear();
}
void AddEdge(int from,int to,int cap,int cost)
{
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int &flow,int &cost)
{
for(int i=0;i<n;++i) d[i]=INF;
queue<int> Q;
memset(inq,0,sizeof(inq));
d[s]=0,inq[s]=true,Q.push(s),a[s]=INF,p[s]=0;
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for(int i=0;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;
a[e.to] = min(a[u],e.cap-e.flow);
p[e.to] = G[u][i];
if(!inq[e.to]){inq[e.to]=true; Q.push(e.to);}
}
}
}
if(d[t]==INF) return false;
flow += a[t];
cost += d[t]*a[t];
int u=t;
while(u!=s)
{
edges[p[u]].flow +=a[t];
edges[p[u]^1].flow -=a[t];
u = edges[p[u]].from;
}
return true;
}
int solve(int num)
{
int flow=0,cost=0;
while(BellmanFord(flow,cost));
return flow ==num ? cost:-1;
}
}MM;
int dist[maxn][maxn];
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;++kase)
{
int n,m,src,dst;
scanf("%d%d",&n,&m);
src=0, dst=2*n+1;
MM.init(2*n+2,src,dst);
memset(dist,-1,sizeof(dist));
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(dist[u][v]==-1 || dist[u][v]>w)
{
dist[u][v]=dist[v][u]=w;
}
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)if(dist[i][j]!=-1)
{
MM.AddEdge(i,j+n,1,dist[i][j]);
MM.AddEdge(j,i+n,1,dist[i][j]);
}
for(int i=1;i<=n;++i)
{
MM.AddEdge(src,i,1,0);
MM.AddEdge(i+n,dst,1,0);
}
int ans=MM.solve(n);
if(ans==-1) printf("Case %d: NO\n",kase);
else printf("Case %d: %d\n",kase,ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu_2102_passed_sorce
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
HDU图论题目分类