poj3068 "Shortest" pair of paths

传送门

好像以前做过qwq

有点像传纸条区别就是人家给个矩阵...

先把原问题考虑成所有边只能走一次

按照套路就是一个费用流吧

里面的每个边流量是1 然后s->1 n->t 连一个费用0流量2

跑完如果最大流不是2那么就没方案

Code:

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<queue>
  6 #define ms(a,b) memset(a,b,sizeof a)
  7 #define rep(i,a,n) for(int i = a;i <= n;i++)
  8 #define per(i,n,a) for(int i = n;i >= a;i--)
  9 #define inf 2147483647
 10 using namespace std;
 11 typedef long long ll;
 12 typedef double D;
 13 #define eps 1e-8
 14 ll read() {
 15     ll as = 0,fu = 1;
 16     char c = getchar();
 17     while(c < '0' || c > '9') {
 18         if(c == '-') fu = -1;
 19         c = getchar();
 20     }
 21     while(c >= '0' && c <= '9') {
 22         as = as * 10 + c - '0';
 23         c = getchar();
 24     }
 25     return as * fu;
 26 }
 27 const int N = 1005;
 28 const int M = 20005;
 29 //head
 30 int s = N-1,t = N-2;
 31 int head[N],nxt[M],mo[M],cnt = 1;
 32 ll cst[M],flw[M];
 33 void _add(int x,int y,ll c,ll f) {
 34     mo[++cnt] = y;
 35     nxt[cnt] = head[x];
 36     head[x] = cnt;
 37     cst[cnt] = c,flw[cnt] = f;
 38 }
 39 void add(int x,int y,ll c,ll f) {
 40     if(x^y) _add(x,y,c,f),_add(y,x,-c,0);
 41 }
 42 
 43 ll dis[N],flow[N];
 44 bool vis[N];
 45 int pre[N],lst[N];
 46 bool spfa() {
 47     queue<int> q;
 48     ms(dis,70),ms(vis,0),ms(flow,70);
 49     dis[s] = 0,q.push(s),vis[s] = 1;
 50     pre[t] = 0;
 51     while(!q.empty()) {
 52         int x = q.front();
 53         q.pop(),vis[x] = 0;
 54         for(int i = head[x];i;i = nxt[i]) {
 55             int sn = mo[i];
 56             if(dis[sn] > dis[x] + cst[i] && flw[i]) {
 57                 dis[sn] = dis[x] + cst[i];
 58                 pre[sn] = x,lst[sn] = i;
 59                 flow[sn] = min(flow[x],flw[i]);
 60                 if(!vis[sn]) vis[sn] = 1,q.push(sn);
 61             }
 62         }
 63     }
 64     return pre[t];
 65 }
 66 
 67 ll maxx,minn;
 68 void MCMF() {
 69     maxx = minn = 0;
 70     while(spfa()) {
 71         int x = t;
 72         maxx += flow[t],minn += flow[t] * dis[t];
 73         while(x ^ s) {
 74             flw[lst[x]] -= flow[t];
 75             flw[lst[x] ^ 1] += flow[t];
 76             x = pre[x];
 77         }
 78     }
 79 }
 80 
 81 int n,m;
 82 void build() {
 83     ms(head,0),cnt = 1;
 84     add(s,1,0,2),add(n,t,0,2);
 85     rep(i,1,m) {
 86         int x = read() + 1,y = read() + 1;
 87         ll w = read();
 88         add(x,y,w,1);
 89     }
 90 }
 91 
 92 int main() {
 93     int T = 0;
 94     while(~scanf("%d%d",&n,&m) && m && n) {
 95         build(),MCMF();
 96         if(maxx < 2) printf("Instance #%d: Not possible
",++T);
 97         else printf("Instance #%d: %lld
",++T,minn);
 98     }
 99     return 0;
100 }