题目

{% raw %}

点击显/隐题目

{% endraw %} 每当西瓜的朋友来西瓜家看他，西瓜总是喜欢带他们逛自己的豪宅。西瓜的豪宅有N幢楼（1<=N<=1000），用1到N的整数编号。1号楼是西瓜豪宅的大门，N号楼是西瓜的储藏室。西瓜的豪宅里总共有M条道路（1<=M<=10000）。每条道路连接两栋不同的楼房，道路的长度不超过35000。为了最好地炫耀他的豪宅，西瓜准备从大门出发，经过一些楼房到达储藏室，再经过一些楼房回到自己的大门。他要求他的路径越短越好，但是不能经过任意一条道路多于一次。请你计算这样的一条最短路径。西瓜保证这样的路径是存在的。

{% raw %}

{% endraw %}

第一行：N和M
第2..M+1行：每行三个整数表示一条道路（起点，终点，长度）

{% raw %}

{% endraw %}

一个整数，表示最短路径长度

{% raw %}

{% endraw %}

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

{% raw %}

{% endraw %}

{% raw %}

{% endraw %}

题解

本次最难的一题
要求是对于一个无向图,在每条路只走一次的情况下,从起点到终点再返回起点的最短路
看到最短路,很容易就想到 BFS ,由于每条路有一定的权值,因此需要用 Dijkstra

很显然的思路,而且能通过样例
但是如果仔细分析样例就能发现有很大的问题存在

可以很容易看出来,去的时候最短路是 3
回来的时候最短路也是 3

但是,如果单纯只是删掉第一次最短路途径的边去跑第二次最短路,有可能就会出现问题
比如,如果第一次最短路走的是 1-2-3-4 这条路,那么第二次时压根就无法返回起点

也就是说,存在有多个最短路有重边的情况
这个问题导致了单纯的搜是不行的

图论问题,不会不如试下网络流

套用网络流的概念来分析下试试

最短路 = 最小费用
每个边一次 = 流量为1

看上去好像没有问题,再深入分析下
最小费用的是 最小费用最大流
它求的是在所有最大流中费用最小的

那么我们先要限定流量
由于每个边只能走一次,边的流量显然是 1
如何体现去回两次呢?
可以在建一个源点,这个源点往外的流量为 2 ,将它连在起点或终点上,然后跑它到另一个点的最小费用最大流

由于其他点的流量都是 1 ,这个节点往外的流量是 2 ,因此只要有解,最大流必然为 2
此时建的图已经和题意的图存在一些差别了
可以看作从起点走两条完全不同的路(每条路的流量为 1 )到终点(汇点流量为 2 )

建图完毕,套用模板

匡斌的模板里点的编号是 0~n-1
因此加边的时候要把 u 和 v 分别减去 1
初始化的时候记得加上汇点

输出最小的费用即可

代码

点击显/隐代码

```cpp FJ的旅行 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include #include #include #include using namespace std;

const int MAXN = 1005;
const int MAXM = 10005;
const int INF = 0x3f3f3f3f;
struct Edge {
int to,next,cap,flow,cost;
}edge[MAXM];

int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n){
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost) {
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t) {
queueq;
for(int i = 0;i < N;i++) {
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1;i = edge[i].next){
int v = edge[i].to;
if(edge[i].cap > edge[i].flow &&
dis[v] > dis[u] + edge[i].cost ){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost) {
int flow = 0;
cost = 0;
while(spfa(s,t)){
int Min = INF;
for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int n, m;
while(cin>>n>>m){
    init(n+1);
    for(int i=0;i<m;i++){
        int u,v,cost;
        cin >> u >> v >> cost;
        addedge(u-1,v-1,1,cost);
        addedge(v-1,u-1,1,cost);
    }
    addedge(n-1,n,2,0);
    int ans=0;
    minCostMaxflow(0,n,ans);
    cout << ans << endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

AOJ 835.FJ的旅行

题目

题解

代码