HDU 4067 Random Maze - c++编程基础

题意：

一幅“随机图”定义为有如下性质的图：

有一个入口和一个出口

有向图

对于入口出度比入度大1

对于出口入度比出度大1

对于其他点入度等于出度

现给出一幅有向图每条边有2个决策――留下、扔掉分别花费a和b 问如果用最少的费用改造出“随机图”

思路：

网络流不错的题目如果做过“混合图欧拉回路”（后文把这个问题成为p）那个zoj的题的话这道题会有启发

来回忆p的做法先将无向边随意定向再利用度来将点划分成二分图利用无向边建边利用度连接这些点与源汇然后做maxflow 满流则有解

“随意定向”启发我们本题也可以对边进行一定的处理因此我们可以先比较a和b 取其中小的状态这样得到的一定是费用最小的决策但不保证是“随机图” 那么此时我们只需要改变决策在费用最小的情况下达到“随机图” 此时想到了费用流

“利用度构图”启发我们同样讨论 in>out in==out in out 的点我们与S连边对于 in

虽然我们的图不是二分图但是层次关系仍然明显

我们将m条输入的边按照a和b的大小关系分别建边u->v 容量1 费用b-a 表示将边从留下状态改为扔掉状态反之亦然

那么此时流量就表示通过更改边的策略能将多少“度”平衡掉也就是说如果maxflow满流则可以构成“随机图”

剩下的就是最小费用很明显就是刚才建边的费用之和最后费用+“随即定向”时的最小花费就是答案

PS：要尽量去理解网络流中“流”的实际意义想办法构造图

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; typedef long long LL; #define N 110 #define M 2010 #define inf (1<<20) int casnum, cas, n, m, s, t, S, T, ans, tot, flow, totflow, cost; int head[N], pre[N], vis[N], dis[N], din[N], dout[N], temp[N]; struct edge { int u, v, w, c, next; } ed[N * M]; queue
              
                qu; void init() { S = 0; T = n + 1; ans = 0; tot = 0; totflow = 0; flow = 0; cost = 0; memset(head, -1, sizeof(head)); memset(din, 0, sizeof(din)); memset(dout, 0, sizeof(dout)); } void add(int U, int V, int W, int C) { ed[tot].u = U; ed[tot].v = V; ed[tot].w = W; ed[tot].c = C; ed[tot].next = head[U]; head[U] = tot++; ed[tot].u = V; ed[tot].v = U; ed[tot].w = 0; ed[tot].c = -C; ed[tot].next = head[V]; head[V] = tot++; } int spfa() { int i, u, v; while (!qu.empty()) qu.pop(); for (i = 0; i <= T; i++) { vis[i] = 0; dis[i] = inf; pre[i] = -1; } qu.push(S); vis[S] = 1; dis[S] = 0; while (!qu.empty()) { u = qu.front(); qu.pop(); vis[u] = 0; for (i = head[u]; ~i; i = ed[i].next) { if (!ed[i].w) continue; v = ed[i].v; if (dis[v] > dis[u] + ed[i].c) { dis[v] = dis[u] + ed[i].c; pre[v] = i; if (!vis[v]) { vis[v] = 1; qu.push(v); } } } } return dis[T] != inf; } void mcmf() { int i, tmp; while (spfa()) { tmp = inf; for (i = pre[T]; ~i; i = pre[ed[i].u]) { if (tmp > ed[i].w) tmp = ed[i].w; } for (i = pre[T]; ~i; i = pre[ed[i].u]) { ed[i].w -= tmp; ed[i ^ 1].w += tmp; cost += tmp * ed[i].c; } flow += tmp; } } struct input { int u, v, a, b; } f[M]; int main() { int i, u, v, a, b; scanf("%d", &casnum); for (cas = 1; cas <= casnum; cas++) { scanf("%d%d%d%d", &n, &m, &s, &t); init(); for (i = 1; i <= m; i++) { scanf("%d%d%d%d", &u, &v, &a, &b); f[i].u = u; f[i].v = v; f[i].a = a; f[i].b = b; if (a < b) { //stay ans += a; din[v]++; dout[u]++; add(u, v, 1, f[i].b - f[i].a); } else { ans += b; //remove add(v, u, 1, f[i].a - f[i].b); } } for (i = 1; i <= n; i++) { temp[i] = dout[i] - din[i]; if (i == s) temp[i]--; else if (i == t) temp[i]++; if (temp[i] > 0) { add(S, i, temp[i], 0); totflow += temp[i]; } else if (temp[i] < 0) add(i, T, -temp[i], 0); } mcmf(); printf("Case %d: ", cas); if (totflow == flow) printf("%d\n", ans + cost); else printf("impossible\n"); } return 0; }