Pagini recente » Cod sursa (job #1474700) | Cod sursa (job #2061097) | Cod sursa (job #252645) | Cod sursa (job #251546)
Cod sursa(job #251546)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 1024
#define pb push_back
using namespace std;
short nrNod, nrVert;
vector <short> vctSol, lVecini[MAX];
short vctTata[MAX];
short matCapac[MAX][MAX], matFlux[MAX][MAX];
inline bool bfs(int source, int dest, int ver)
{
queue <short> queBfs;
queBfs.push(source);
memset(vctTata, 0, sizeof(vctTata));
vctTata[source] = -1;
for (; !queBfs.empty(); queBfs.pop())
for (int i = 0, nod = queBfs.front(); i < lVecini[nod].size(); i++)
if (!vctTata[lVecini[nod][i]] && matCapac[nod][lVecini[nod][i]] > matFlux[nod][lVecini[nod][i]])
{
queBfs.push(lVecini[nod][i]);
vctTata[lVecini[nod][i]] = nod;
if (lVecini[nod][i] == dest && ver)
return 1;
}
return vctTata[dest] != 0;
}
inline void flux(int source, int dest)
{
for (; bfs(source, dest, 0); )
for (int nod = 1; nod <= nrNod; nod++)
{
if (vctTata[nod] <= 0 || matCapac[nod][dest] - matFlux[nod][dest] <= 0)
continue;
int r = matCapac[nod][dest] - matFlux[nod][dest];
for (int i = nod; i != source; i = vctTata[i])
r = min(r, matCapac[vctTata[i]][i] - matFlux[vctTata[i]][i]);
matFlux[nod][dest] += r;
matFlux[dest][nod] -= r;
for (int i = nod; i != source; i = vctTata[i])
{
matFlux[vctTata[i]][i] += r;
matFlux[i][vctTata[i]] -= r;
}
}
}
int main()
{
freopen("critice.in", "r", stdin);
freopen("critice.out", "w", stdout);
scanf("%d %d", &nrNod, &nrVert);
for (int i = 1; i <= nrVert; i++)
{
int node1, node2, capac;
scanf("%d %d %d", &node1, &node2, &capac);
matCapac[node1][node2] = matCapac[node2][node1] = capac;
lVecini[node1].pb(node2);
lVecini[node2].pb(node1);
}
flux(1, nrNod);
fclose(stdin);
freopen("critice.in", "r", stdin);
scanf("%d %d", &nrNod, &nrVert);
for (int i = 1; i <= nrVert; i++)
{
int node1, node2, capac;
scanf("%d %d %d", &node1, &node2, &capac);
matCapac[node1][node2] = matCapac[node2][node1] = capac + 1;
if (bfs(1, nrNod, 1))
vctSol.pb(i);
matCapac[node1][node2] = matCapac[node2][node1] = capac;
}
printf("%d\n", vctSol.size());
for (int i = 0; i < vctSol.size(); i++)
printf("%d\n", vctSol[i]);
fclose(stdin);
fclose(stdout);
return 0;
}