poj 3068 "Shortest" pair of paths

"Shortest" pair of paths

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1407		Accepted: 627

Description

A chemical company has an unusual shortest path problem.

There are N depots (vertices) where chemicals can be stored. There are M individual shipping methods (edges) connecting pairs of depots. Each individual shipping method has a cost. In the usual problem, the company would need to find a way to route a single shipment from the first depot (0) to the last (N - 1). That's easy. The problem they have seems harder. They have to ship two chemicals from the first depot (0) to the last (N - 1). The chemicals are dangerous and cannot safely be placed together. The regulations say the company cannot use the same shipping method for both chemicals. Further, the company cannot place the two chemicals in same depot (for any length of time) without special storage handling --- available only at the first and last depots. To begin, they need to know if it's possible to ship both chemicals under these constraints. Next, they need to find the least cost of shipping both chemicals from first depot to the last depot. In brief, they need two completely separate paths (from the first depot to the last) where the overall cost of both is minimal.

Your program must simply determine the minimum cost or, if it's not possible, conclusively state that the shipment cannot be made.

Input

The input will consist of multiple cases. The first line of each input will contain N and M where N is the number of depots and M is the number of individual shipping methods. You may assume that N is less than 64 and that M is less than 10000. The next M lines will contain three values, i, j, and v. Each line corresponds a single, unique shipping method. The values i and j are the indices of two depots, and v is the cost of getting from i to j. Note that these shipping methods are directed. If something can be shipped from i to j with cost 10, that says nothing about shipping from j to i. Also, there may be more than one way to ship between any pair of depots, and that may be important here.
A line containing two zeroes signals the end of data and should not be processed.

Output

follow the output format of sample output.

Sample Input

Sample Output

Instance #1: Not possible
Instance #2: 40
Instance #3: 73

题意：从入口到出口，同时运送两批化学药品，且规定两批药品运送过程中都不能经过任意一条一样的路(即一批药经过的路另一批药运送不能经过)，且使得运送两批药品的总路程尽量小，应该是多少。
思路：建立源点S，S到路口连费用0，流量2的边，建立汇点t,终点到t也建立流量为2费用0的边，中间的图的流量都为1，建图，求最小费用流即可。
AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>
#include<cstring>
#include<string>
#include<functional>
using namespace std;
#define INF 0x3f3f3f3f
const int N_MAX = 70,V_MAX=70;

typedef pair<int, int>P;
struct edge { int to, cap, cost, rev;
edge(int to=0,int cap=0,int cost=0,int rev=0):to(to),cap(cap),cost(cost),rev(rev) {}
};
int V;
vector<edge>G[V_MAX];
int h[V_MAX];
int dist[V_MAX];
int prevv[V_MAX], preve[V_MAX];

void add_edge(int from,int to,int cap,int cost) {
    G[from].push_back(edge(to,cap,cost,G[to].size()));
    G[to].push_back(edge(from,0,-cost,G[from].size()-1));
}
//没流量则返回-1
int min_cost_flow(int s,int t,int f) {
    int res = 0;
    fill(h, h + V, 0);
    while (f>0) {
        priority_queue<P, vector<P>, greater<P> >que;
        fill(dist,dist+V,INF);
        dist[s] = 0;
        que.push(P(0,s));
        while (!que.empty()) {
            P p = que.top(); que.pop();
            int v = p.second;
            if (dist[v] < p.first)continue;
            for (int i = 0; i < G[v].size();i++) {
                edge&e = G[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(P(dist[e.to],e.to));
                }
            }
        }
        if (dist[t] == INF)return -1; 
        for (int v = 0; v < V; v++)h[v] += dist[v];
        int d = f;
        for (int v = t; v != s;v=prevv[v]) {
            d = min(d,G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d*h[t];
        for (int v = t; v != s;v=prevv[v]) {
            edge&e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

void clear() {
    for (int i = 0; i < V;i++) {
        G[i].clear();
    }
}

int N, M;

int main() {
    int cs=0;
    while (scanf("%d%d",&N,&M)&&N) {
        int s = N, t = s + 1;
        V = t+1;
        for (int i = 0; i < M;i++) {
            int u, v, cost;
            scanf("%d%d%d",&u,&v,&cost);
            add_edge(u,v,1,cost);
        }
        add_edge(s, 0, 2, 0);
        add_edge(N-1,t,2,0);
        int res = min_cost_flow(s, t, 2);
        printf("Instance #%d: ", ++cs);
        if(res!=-1)printf("%d
",res);
        else printf("Not possible
");
        clear();
    }
    return 0;
}