Pagini recente » Cod sursa (job #1742086) | Cod sursa (job #451778) | Cod sursa (job #463836) | Cod sursa (job #220405) | Cod sursa (job #1389479)
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int ;
class graph
{
public:
int N, S, D, t[1009], f[1009][1009], c[1009][1009];
vector < int > v[1009];
void add_edge (int x, int y, int cap)
{
c[x][y] = cap;
v[x].push_back (y);
v[y].push_back (x);
}
bool bfs ()
{
queue < int > cc;
for (int i=1; i<=N; i++)
t[i] = -1;
cc.push (S);
t[S] = 0;
while (!cc.empty())
{
int nod = cc.front ();
cc.pop();
for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
if (t[*it] == -1 && f[nod][*it] < c[nod][*it])
{
t[*it] = nod;
cc.push (*it);
if (*it == D)
return 1;
}
}
return 0;
}
int flux ()
{
int F = 0;
while (bfs ())
{
for (vector < int > :: iterator it = v[D].begin(); it != v[D].end(); it ++)
if (f[*it][D] < c[*it][D])
{
int mini = 1000000;
t[D] = *it;
for (int i=D; i != S; i = t[i])
if (c[t[i]][i] - f[t[i]][i] < mini)
mini = c[t[i]][i] - f[t[i]][i];
F += mini;
for (int i=D; i != S; i = t[i])
{
f[t[i]][i] += mini;
f[i][t[i]] -= mini;
}
}
}
return F;
}
};
int main()
{
freopen ("pixels.in", "r", stdin);
freopen ("pixels.out", "w", stdout);
return 0;
}