Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 开数组时注意反向边！！！附瞎写的dinic

Posted by _Konpaku at 2018-04-26 23:00:12 on Problem 1273
```#include <cstdio>
#include <queue>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct E
{
int u, v, f;
E() {};
E(int a, int b, int c) { u = a; v = b; f = c; }
}edge[500];
const int inf = 0x3f3f3f3f;
int n, m;
int s[500][500];//边集
int t;//总边数(含反向边)
int cur[500]; //当前弧
int dis[500]; //分层

void add(int u, int v, int f)
{
s[u][0]++;
s[u][s[u][0]] = t;
edge[t++] = E(u, v, f);
s[v][0]++;
s[v][s[v][0]] = t;
edge[t++] = E(v, u, 0);
}

bool bfs()
{
queue<int> q;
for (int i = 1; i <= m; i++)
{
dis[i] = 0;
}
dis[1] = 1;
q.push(1);

while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = 1; i <= s[now][0]; i++)
{
E &temp = edge[s[now][i]];
//cout << i << ends << now << ends << temp.v << endl;
if (temp.f && !dis[temp.v])
{
//cout << "1" << endl;
dis[temp.v] = dis[now] + 1;
q.push(temp.v);
}
}
}

return dis[m];
}

int dfs(int index, int flow)//起点 , 流量
{
if (index == m)
return flow;

if (!cur[index])
cur[index] = 1;
for (int i = cur[index]; i <= s[index][0]; i++)
{
E &e = edge[s[index][i]];
E &e1 = edge[s[index][i] ^ 1];
if (e.f > 0 && dis[e.v] == dis[index] + 1)
{
int x = dfs(e.v, min(flow, e.f));
if (x > 0)
{
e.f -= x;
e1.f += x;
cur[index] = i;
return x;
}
}
}

return 0;
}

int dinic()
{
int sum = 0, num;
while (bfs())
{
memset(cur, 0, sizeof(cur));
do
{
num = dfs(1,inf);
sum += num;
} while (!num);
}

return sum;
}

int main()
{
while (~scanf("%d %d", &n, &m))
{
for (int i = 0; i <= m; i++)
s[i][0] = 0;

t = 0;
for (int i = 0; i < n; i++)
{
int u, v, f;
scanf("%d %d %d", &u, &v, &f);
}
printf("%d\n", dinic());
}
return 0;
}```

Followed by: