当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 P1P2，再把图中除了这条边以外的边，每一条的权值都减少1。如图 4所示就是一次这样的操作：

输出文件只有一行，这行只有一个整数，即，使得标号为Lab边一定出现最小生成树中的最少操作次数。

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D<10^6

day2

  1 #include <cstdio>  2 #include <cstring>  3   4 inline char nextChar(void)  5 {  6     static const int siz = 1 << 20;  7       8     static char buf[siz];  9     static char *hd = buf + siz; 10     static char *tl = buf + siz; 11      12     if (hd == tl) 13         fread(hd = buf, 1, siz, stdin); 14      15     return *hd++; 16 } 17  18 inline int nextInt(void) 19 { 20     register int ret = 0; 21     register bool neg = false; 22     register char bit = nextChar(); 23      24     for (; bit < 48; bit = nextChar()); 25         if (bit == ‘-‘)neg ^= true; 26      27     for (; bit > 47; bit = nextChar()) 28         ret = ret * 10 + bit - ‘0‘; 29      30     return neg ? -ret : ret; 31 } 32  33 const int siz = 2005; 34 const int edg = 2e6 + 5; 35 const int inf = 2e9 + 7; 36  37 int n, m, id, s, t; 38  39 struct edge 40 { 41     int x, y, w; 42 }e[edg]; 43  44 int hd[siz], to[edg], nt[edg], fl[edg], tot; 45  46 inline void add(int u, int v, int f) 47 { 48     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; hd[u] = tot++; 49     nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; hd[v] = tot++; 50 } 51  52 int dep[siz]; 53  54 inline bool bfs(void) 55 { 56     static int que[siz]; 57     static int head, tail; 58      59     memset(dep, 0, sizeof(dep)); 60      61     que[head = 0] = s, tail = dep[s] = 1; 62      63     while (head != tail) 64     { 65         int u = que[head++], v; 66          67         for (int i = hd[u]; ~i; i = nt[i]) 68             if (!dep[v = to[i]] && fl[i]) 69                 dep[que[tail++] = v] = dep[u] + 1; 70     } 71      72     return dep[t]; 73 } 74  75 int cur[siz]; 76  77 inline int min(int a, int b) 78 { 79     return a < b ? a : b; 80 } 81  82 int dfs(int u, int f) 83 { 84     if (!f || u == t) 85         return f; 86      87     int used = 0, flow, v; 88      89     for (int i = cur[u]; ~i; i = nt[i]) 90         if (dep[v = to[i]] == dep[u] + 1 && fl[i]) 91         { 92             flow = dfs(v, min(fl[i], f - used)); 93              94             used += flow; 95             fl[i] -= flow; 96             fl[i^1] += flow; 97              98             if (fl[i]) 99                 cur[u] = i;100             101             if (used == f)102                 return f;103         }104     105     if (!used)106         dep[u] = 0;107     108     return used;109 }110 111 inline int minCut(void)112 {113     int minCut = 0, newFlow;114     115     while (bfs())116     {117         memcpy(cur, hd, sizeof(hd));118         119         while (newFlow = dfs(s, inf))120             minCut += newFlow;121     }122     123     return minCut;124 }125 126 signed main(void)127 {128     n = nextInt();129     m = nextInt();130     131     id = nextInt();132     133     for (int i = 1; i <= m; ++i)134     {135         e[i].x = nextInt();136         e[i].y = nextInt();137         e[i].w = nextInt();138     }139     140     s = e[id].x;141     t = e[id].y;142     143     int lim = e[id].w;144     145     memset(hd, -1, sizeof(hd));146     147     for (int i = 1; i <= m; ++i)148         if (e[i].w <= lim && i != id)149             add(e[i].x, e[i].y, lim + 1 - e[i].w),150             add(e[i].y, e[i].x, lim + 1 - e[i].w);151         152     printf("%d\n", minCut());153 }