1 #include2 #include 3 #include 4 #include 5 #define INF 0x3f3f3f3f 6 #define MAXN 10010 7 #define MAXM 300010 8 using namespace std; 9 int n, m, s, t, tot = 1;10 int beginx[MAXN], endx[MAXM], nxt[MAXM], res[MAXM];11 inline void add_edge(int u, int v, int w)12 {13 nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, res[tot] = w;14 nxt[++tot] = beginx[v], beginx[v] = tot, endx[tot] = u, res[tot] = 0;15 }16 struct PQ17 {18 int x,h;19 PQ(int _x,int _h)20 {21 x = _x, h = _h;22 }23 bool operator < (const PQ &tar) const24 {25 return h < tar.h;26 }27 };28 int gap[MAXN], d[MAXN], ans[MAXN];29 inline bool push(int x, int y, int ptr)30 {31 int w = min(ans[x], res[ptr]);32 res[ptr] -= w, res[ptr^1] += w;33 ans[x] -= w, ans[y] += w;34 return w;35 }36 inline void Gap(int val)37 {38 for (int i = 1; i <= n; ++i)39 if(i != s && i != t && val < d[i] && d[i] <= n)40 d[i] = n + 1;41 }42 inline int HLPP()43 {44 priority_queue pq;45 d[s] = n, ans[s] = INF, pq.push(PQ(s, d[s]));46 int u;47 while(!pq.empty())48 {49 u = pq.top().x, pq.pop();50 if(!ans[u]) continue;51 for(int i = beginx[u], v = endx[i]; i; i = nxt[i], v = endx[i])52 if((u == s || d[u] == d[v] + 1) && push(u, v, i) && v != t && v != s)53 pq.push(PQ(v, d[v]));54 if (u != s && u != t && ans[u]) 55 {56 if(!(--gap[d[u]])) Gap(d[u]);57 ++gap[++d[u]];58 pq.push(PQ(u, d[u]));59 }60 }61 return ans[t];62 }63 int main()64 {65 scanf("%d%d%d%d",&n,&m,&s,&t);66 for(int i = 1; i <= m; i++)67 {68 int u,v,r;69 scanf("%d%d%d",&u,&v,&r);70 add_edge(u, v, r);71 }72 printf("%d", HLPP());73 return 0;74 }
主程序仅有35行，可能会TLE，需要卡卡常数。
暴露出的问题：
- priority_queue太慢，用pq比普通队列还慢。
- STL效率差到爆炸，明明是需要多次BFS，入队出队次数很多，然而效率低，没办法，卡死了。
1 #include2 #include 3 using namespace std; 4 #define MAXN 10005 5 #define MAXM 200010 6 #define INF 0x3f3f3f3f 7 8 inline char get_char() 9 { 10 static char buf[1000001], *p1 = buf, *p2 = buf; 11 return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++; 12 } 13 inline int read() 14 { 15 register int num = 0; 16 char c; 17 while (isspace(c = get_char())); 18 while (num = num * 10 + c - 48, isdigit(c = get_char())); 19 return num; 20 } 21 inline void upmin(int &a, const int &b) 22 { 23 if(a > b) a = b; 24 } 25 26 int beginx[MAXN], endx[MAXM], nxt[MAXM], res[MAXM]; 27 28 struct Q 29 { 30 int s, t; 31 Q() 32 { 33 s = 1 , t = 0; 34 } 35 int q[MAXM]; 36 inline bool empty() 37 { 38 return s > t; 39 } 40 inline int front() 41 { 42 return q[s++]; 43 } 44 inline void push(int tar) 45 { 46 q[++t] = tar; 47 } 48 } mession; 49 50 int main() 51 { 52 register int n = read(), m = read(), s = read(), t = read(), tot = 1; 53 for(int i = 1; i <= m; i++) 54 { 55 int u = read(), v = read(), c = read(); 56 nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, res[tot] = c; 57 nxt[++tot] = beginx[v], beginx[v] = tot, endx[tot] = u, res[tot] = 0; 58 } 59 register int ar = s, r = INF, ans = 0; 60 bool done; 61 int d[MAXN], num[MAXN], cur[MAXN], pre[MAXN]; 62 mession.push(t); 63 d[t] = 1; 64 register int u, v; 65 while(!mession.empty()) 66 { 67 u = mession.front(); 68 num[d[u]]++; 69 for(int i = beginx[u]; i; i = nxt[i]) 70 { 71 v = endx[i]; 72 if(!d[v] && res[i ^ 1]) 73 { 74 d[v] = d[u] + 1; 75 mession.push(v); 76 } 77 } 78 } 79 for(int i = 1; i <= n; i++) cur[i] = beginx[i]; 80 while(d[s] != n + 1) 81 { 82 if(ar == t) 83 { 84 while(ar != s) 85 { 86 res[pre[ar]] -= r, res[pre[ar] ^ 1] += r; 87 ar = endx[pre[ar] ^ 1]; 88 } 89 ans += r, r = INF; 90 } 91 done = false; 92 for(int &i = cur[ar]; i; i = nxt[i]) 93 { 94 int v = endx[i]; 95 if(res[i] && d[v] == d[ar] - 1) 96 { 97 done = true, pre[v] = i, ar = v; 98 upmin(r, res[i]); 99 break;100 }101 }102 if(!done)103 {104 register int heig = n + 1;105 for(int i = beginx[ar]; i; i = nxt[i])106 {107 int v = endx[i];108 if(res[i]) upmin(heig, d[v] + 1);109 }110 if(--num[d[ar]] == 0) break;111 cur[ar] = beginx[ar];112 num[d[ar] = heig]++;113 if(ar != s) ar = endx[pre[ar] ^ 1];114 }115 }116 printf("%d", ans);117 return 0;118 }