【BZOJ3931】[CQOI2015]网络吞吐量

Description

路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。

Input

输入文件第一行包含两个空格分开的正整数n和m，分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行，每行包含三个空格分开的正整数a、b和d，表示从路由器a到路由器b存在一条距离为d的双向链路。接下来n行，每行包含一个正整数c，分别给出每一个路由器的吞吐量。

Output

输出一个整数，为题目所求吞吐量。

Sample Input

7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

Sample Output

HINT

对于100%的数据，n≤500，m≤100000，d,c≤10^9

Solution

其实看懂题目应该就会做了吧？题目的意思应该就是题解了。。。

意思就是说只有在最短路上的边才能流，每个点有流量限制（除了1和N），求1到N的最大流。

所以直接按题意模拟即可。

Code

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 #ifdef WIN32

     #define LL "%I64d"

 #else

     #define LL "%lld"

 #endif

 #ifdef CT

     #define debug(...) printf(__VA_ARGS__)

     #define setfile()

 #else

     #define debug(...)

     #define filename ""

     #define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout)

 #endif

 #define R register

 #define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)

 #define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)

 #define cabs(_x) ((_x) < 0 ? (- (_x)) : (_x))

 char B[ << ], *S = B, *T = B;

 inline int F()

 {

     R char ch; R int cnt = ; R bool minus = ;

     while (ch = getc(), (ch < '' || ch > '') && ch != '-') ;

     ch == '-' ? minus =  : cnt = ch - '';

     while (ch = getc(), ch >= '' && ch <= '') cnt = cnt *  + ch - '';

     return minus ? -cnt : cnt;

 }

 #define maxn 10010

 #define maxm 1000010

 struct edge

 {

     int a, b, w;

 }ee[maxm];

 struct Edge

 {

     Edge *next, *rev;

     int to, cap;

 }*last[maxn], e[maxm], *ecnt = e, *cur[maxn];

 inline void link(R int a, R int b, R int w)

 {

     *++ecnt = (Edge) {last[a], ecnt + , b, w}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], ecnt - , a, }; last[b] = ecnt;

 }

 inline void link2(R int a, R int b, R int w)

 {

     *++ecnt = (Edge) {last[a], ecnt + , b, w}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], ecnt - , a, w}; last[b] = ecnt;

 }

 std::queue<int> q;

 #define inf 0x7fffffff

 int dep[maxn], s, t;

 long long dis[maxn], ans;

 bool inq[maxn];

 inline void spfa()

 {

     memset(dis, , sizeof (dis));

     dis[s] = ; q.push(s);

     while (!q.empty())

     {

         R int now = q.front(); q.pop(); inq[now] = ;

         for (R Edge *iter = last[now]; iter; iter = iter -> next)

         {

             R int pre = iter -> to;

             if (dis[pre] > dis[now] + iter -> cap)

             {

                 dis[pre] = dis[now] + iter -> cap;

                 if (!inq[pre])

                 {

                     q.push(pre);

                     inq[pre] = ;

                 }

             }

         }

     }

 }

 int id[maxn][];

 inline bool bfs()

 {

     memset(dep, -, sizeof (dep));

     dep[t] = ; q.push(t);

     while (!q.empty())

     {

         R int now = q.front(); q.pop();

         for (R Edge *iter = last[now]; iter; iter = iter -> next)

         {

             R int pre = iter -> to;

             if (iter -> rev -> cap && dep[pre] == -)

             {

                 dep[pre] = dep[now] + ;

                 q.push(pre);

             }

         }

     }

     return dep[s] != -;

 }

 int dfs(R int x, R int f)

 {

     if (x == t) return f;

     R int used = ;

     for (R Edge* &iter = cur[x]; iter; iter = iter -> next)

     {

         R int pre = iter -> to;

         if (iter -> cap && dep[x] == dep[pre] + )

         {

             R int v = dfs(pre, dmin(iter -> cap, f - used));

             iter -> cap -= v;

             iter -> rev -> cap += v;

             used += v;

             if (f == used) return f;

         }

     }

     if (!used) dep[x] = -;

     return used;

 }

 inline void dinic()

 {

     while (bfs())

     {

         memcpy(cur, last, sizeof last);

         ans += dfs(s, inf);

     }

 }

 int main()

 {

 //    setfile();

     R int n = F(), m = F(), cnt = ;

     for (R int i = ; i <= m; ++i)

     {

         R int a, b, w;

         ee[i] = (edge) {a = F(), b = F(), w = F()};

         link2(a, b, w);

     }

     s = ;

     spfa();

     memset(last, , sizeof last);

     ecnt = e;

     for (R int i = ; i <= n; ++i)

     {

         id[i][] = ++cnt;

         id[i][] = ++cnt;

         link(id[i][], id[i][], F());

     }

     s = id[][]; t = id[n][];

     for (R int i = ; i <= m; ++i)

     {

         if (dis[ee[i].a] == dis[ee[i].b] + ee[i].w)

             link(id[ee[i].b][], id[ee[i].a][], inf);

         if (dis[ee[i].b] == dis[ee[i].a] + ee[i].w)

             link(id[ee[i].a][], id[ee[i].b][], inf);

     }

     dinic();

     printf("%lld\n", ans );

     return ;

 }

巴特西