MashPlant @ 2018-01-28 16:08:26
求助一下,蒟蒻的代码只有80分,WA第5和10个点
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
static char ch;
bool sgn = false;
while ((ch = getchar()) < '0' || ch > '9')
if (ch == '-')
sgn = true;
int res = ch - 48;
while ((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + ch - 48;
return sgn ? -res : res;
}
const int inf = 0x3f3f3f3f;
const int ninf = 0xf3f3f3f3;
struct E
{
int to;
int w;
int another;
};
typedef vector<E> ve;
ve es[10010];
int n, m, s, t;
bool vis[10010];
ll dfs(int x, ll cur)
{
vis[x] = true;
if (!cur || x == t)
return cur;
ve &e = es[x];
for (int i = 0; i < e.size(); ++i)
{
if (e[i].w > 0 && !vis[e[i].to])
if (int add = dfs(e[i].to, min(cur, ll(e[i].w))))
{
e[i].w -= add, es[e[i].to][e[i].another].w += add;
return add; //找出一条增广路就停了
}
}
return 0;
}
int main()
{
n = read(), m = read(), s = read(), t = read();
while (m--)
{
int u = read(), v = read(), w = read();
es[u].push_back({v, w, int(es[v].size())});
es[v].push_back({u, -w, int(es[u].size() - 1)});
}
int ans = 0;
while (int more = dfs(s, inf))
memset(vis, 0, sizeof(vis)), ans += more;
printf("%d\n", ans);
return 0;
}
by MashPlant @ 2018-01-28 16:48:27
好吧我知道了....反向边的初始容量为0.....
虽然没人回复但还是谢谢大家。