本文共 2923 字，大约阅读时间需要 9 分钟。
Dinic解网络流模板题目。队列用STL就TLE。。。
1 /* 3061 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int INF = 1e9; 43 const int maxn = 505; 44 const int maxe = 1111111; 45 int V[maxe], F[maxe], nxt[maxe]; 46 int head[maxn], dis[maxn]; 47 int head_[maxn]; 48 int Q[maxn]; 49 int s, t; 50 int n, m; 51 52 void init(int n_) { 53 memset(head, -1, sizeof(head)); 54 s = m = 0; 55 n = n_ + 2; 56 t = n - 1; 57 } 58 59 void addEdge(int u, int v, int c) { 60 V[m] = v; 61 F[m] = c; 62 nxt[m] = head[u]; 63 head[u] = m++; 64 65 V[m] = u; 66 F[m] = 0; 67 nxt[m] = head[v]; 68 head[v] = m++; 69 } 70 71 bool bfs() { 72 int u, v, k; 73 int l = 0, r = 0; 74 75 memset(dis, -1, sizeof(dis)); 76 dis[s] = 0; 77 Q[r++] = s; 78 79 while(l < r) { 80 u = Q[l++]; 81 for (k=head[u]; k!=-1; k=nxt[k]) { 82 v = V[k]; 83 if (F[k] && dis[v]<0) { 84 dis[v] = dis[u] + 1; 85 if (v == t) 86 return false; 87 Q[r++] = v; 88 } 89 } 90 } 91 92 return true; 93 } 94 95 int dfs(int u, int a) { 96 if (u == t) 97 return a; 98 99 int v, tmp;100 101 for (int& k=head_[u]; k!=-1; k=nxt[k]) {102 v = V[k];103 if (F[k] && dis[v]==dis[u]+1 && (tmp=dfs(v, min(a, F[k])))>0) {104 F[k] -= tmp;105 F[k^1] += tmp;106 return tmp;107 }108 }109 110 return 0;111 }112 113 int Dinic() {114 int ret = 0, tmp;115 116 while (1) {117 if (bfs())118 break;119 memcpy(head_, head, sizeof(head));120 while ((tmp = dfs(s, INF))!=0)121 ret += tmp;122 }123 124 return ret;125 }126 127 int main() {128 ios::sync_with_stdio(false);129 #ifndef ONLINE_JUDGE130 freopen("data.in", "r", stdin);131 freopen("data.out", "w", stdout);132 #endif133 134 int n_, m_;135 int u, v;136 int tot, ans, x;137 138 while (scanf("%d %d", &n_, &m_) != EOF) {139 init(n_);140 tot = 0;141 rep(i, 1, n_+1) {142 scanf("%d", &x);143 if (x > 0) {144 addEdge(s, i, x);145 tot += x;146 } else if (x < 0) {147 addEdge(i, t, -x);148 }149 }150 while (m_--) {151 scanf("%d %d", &u, &v);152 addEdge(u, v, INF);153 }154 ans = Dinic();155 printf("%d\n", tot-ans);156 }157 158 #ifndef ONLINE_JUDGE159 printf("time = %d.\n", (int)clock());160 #endif161 162 return 0;163 }
转载于:https://www.cnblogs.com/bombe1013/p/4873310.html