链接 https://lydsy.com/JudgeOnline/problem.php?id=3931
分析:
跑一遍 dijkstra, 加入可以存在于最短路中的点, 拆点最大流.
代码:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<cctype>
- #include<set>
- #include<queue>
- #include<vector>
- #include<map>
- #define pa pair<LL,int>
- using namespace std;
- typedef long long LL;
- inline int read() {
- int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
- for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
- }
- const int N = 2005;
- const LL INF = 1e18;
- int a[100005], b[100005];LL c[100005];
- namespace Dijkstra{
- LL dis[N]; bool vis[N]; int head[N], En;
- struct Edge{ int to, nxt;LL w; } e[500005];
- void add_edge(int u,int v,LL w) {
- ++En; e[En].to = v, e[En].w = w, e[En].nxt = head[u]; head[u] = En;
- ++En; e[En].to = u, e[En].w = w, e[En].nxt = head[v]; head[v] = En;
- }
- priority_queue<pa, vector< pa>, greater<pa>> q;
- void solve() {
- memset(dis, 0x3f, sizeof(dis));
- dis[1] = 0; q.push(pa(0, 1));
- while (!q.empty()) {
- int u = q.top().second; q.pop();
- if (vis[u]) continue;
- vis[u] = 1;
- for (int i = head[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (dis[v]> dis[u] + e[i].w) {
- dis[v] = dis[u] + e[i].w;
- q.push(pa(dis[v], v));
- }
- }
- }
- }
- }
- namespace Dinic {
- struct Edge{ int to, nxt;LL cap; } e[500005];
- int head[N], cur[N], q[N], dis[N], En = 1, S, T;
- void add_edge(int u,int v,LL w) {
- ++En; e[En].to = v, e[En].cap = w, e[En].nxt = head[u]; head[u] = En;
- ++En; e[En].to = u, e[En].cap = 0, e[En].nxt = head[v]; head[v] = En;
- }
- bool bfs() {
- for (int i = 0; i <= T; ++i) dis[i] = -1, cur[i] = head[i];
- int L = 1, R = 0; q[++R] = S; dis[S] = 0;
- while (L <= R) {
- int u = q[L ++];
- for (int i = head[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (dis[v] == -1 && e[i].cap> 0) {
- dis[v] = dis[u] + 1, q[++R] = v;
- if (v == T) return 1;
- }
- }
- }
- return 0;
- }
- LL dfs(int u,LL flow) {
- if (u == T) return flow;
- LL used = 0, tmp = 0;
- for (int &i = cur[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (dis[v] == dis[u] + 1 && e[i].cap> 0) {
- tmp = dfs(v, min(flow - used, e[i].cap));
- if (tmp> 0) {
- e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
- if (used == flow) break;
- }
- }
- }
- if (used != flow) dis[u] = -1;
- return used;
- }
- LL dinic() {
- LL ans = 0;
- while (bfs()) ans += dfs(S, INF);
- return ans;
- }
- }
- int main() {
- int n = read(), m = read();
- for (int i = 1; i <= m; ++i) {
- a[i] = read(), b[i] = read(), c[i] = read();
- Dijkstra::add_edge(a[i], b[i], c[i]);
- }
- Dijkstra::solve();
- for (int i = 1; i <= m; ++i) {
- if (Dijkstra::dis[a[i]] + c[i] == Dijkstra::dis[b[i]]) {
- Dinic::add_edge(a[i] + n, b[i], INF);
- }
- if (Dijkstra::dis[b[i]] + c[i] == Dijkstra::dis[a[i]]) {
- Dinic::add_edge(b[i] + n, a[i], INF);
- }
- }
- for (int i = 1; i <= n; ++i) {
- int c = read();
- if (i == 1 || i == n) Dinic::add_edge(i, i + n, INF);
- else Dinic::add_edge(i, i + n, c);
- }
- Dinic::S = 1, Dinic::T = n + n;
- cout << Dinic::dinic();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2986685.html