大致题意:
给出一个有向图,每条路都有一个边长值。现在要在图中选出一些圈(回路),使得 1,每个圈至少包含两个点。 2,每个节点只能属于其中一个圈。现在求这些圈的总长度最少是多少。
大致思路:
囧啊,此等水题居然想了半天没有想法,最后又钻到欧拉回路的死胡同里面去了。其实很简单,因为每个点都必须只属于一个圈,所以每个点的入读和出度肯定都是1。把每个点拆成两个点 i i'。从源点向每个点连一条边容量为1,费用为0,限制入度。从每个i'向汇点连边,容量为1,限制出度。如果原图中有一条边(u v)。则连接u->v'容量为1,费用为这条路的长度。最后对构出的图求出最小费用最大流就可以了。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=99999999;
const int nMax=3000;
const int mMax=200000;
struct{
int u,v, cap, cost, next, re;
}edge[mMax];
int ans,maxf;
int k,edgeHead[nMax];
int que[nMax],pre[nMax],dis[nMax];
bool vis[nMax],flag;
int K;
void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费
edge[k].v=v;
edge[k].cap=ca;
edge[k].cost=co;
edge[k].next=edgeHead[u];
edge[k].re=k + 1;
edgeHead[u]=k ++;
edge[k].v=u;
edge[k].cap=0;
edge[k].cost=-co;
edge[k].next=edgeHead[v];
edge[k].re=k - 1;
edgeHead[v]=k ++;
}
bool spfa(int s,int t,int n){ //始点,终点,总点数
int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方
for(i = 0; i <= n; i ++){
dis[i] = inf;////////////
vis[i] = false;
}
dis[s] = 0;
que[0] = s;
vis[s] = true;
while(head != tail){
int u = que[head];
for(i = edgeHead[u]; i != 0; i = edge[i].next){
int v = edge[i].v;
if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){////////
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
que[tail ++] = v;
if(tail == nMax) tail = 0;
}
}
}
vis[u] = false;
head++;
if(head ==nMax) head = 0;
}
if(dis[t] ==inf) return false;///////////
return true;
}
void end(int s,int t){
int u, p;
for(u = t;u!=s;u=edge[edge[p].re].v){
p = pre[u];
edge[p].cap-=1;
edge[edge[p].re].cap+=1;
ans+=edge[p].cost;
}
maxf+=1; //总流量
}
int main(){
int n,m,i,s,t,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF){
k=1;
s=0,t=2*n+1;
memset(edgeHead,0,sizeof(edgeHead));
for(i=1;i<=n;i++){
addEdge(s,i,1,0);
addEdge(i+n,t,1,0);
}
while(m--){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b+n,1,c);
}
ans=0;
maxf=0;
while(spfa(s,t,2*n+2)){
end(s,t);
}
if(maxf!=n){
printf("-1\n");
}
else{
printf("%d\n",ans);
}
}
return 0;
}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
Problem Description Calculate A + B. Input Each line will contain two integers A and B....HDOJ 代码: #include int main() { int a,b; while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); }
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码