Pagini recente » Cod sursa (job #279863) | Cod sursa (job #1352932) | Cod sursa (job #3042175) | Cod sursa (job #2100289) | Cod sursa (job #3032023)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,X,Y,m;
int st,dr;
const int N=205;
int viz[N],last[N];
int d[N][N],flux[N][N];
vector<int>a[N];
bool bfs()
{
for(int i=0;i<=2*n+1;i++)
viz[i]=0,last[i]=-1;
queue<int>q;
q.push(st);
while(!q.empty())
{
int nod=q.front();
q.pop();
if(nod==dr)
continue;
for(auto x: a[nod])
{
// g<<nod<<" "<<x<<'\n';
if(!viz[x]&&d[nod][x]>flux[nod][x])
{
viz[x]=true;
last[x]=nod;
q.push(x);
}
}
}
return viz[dr];
}
int main()
{
f>>n;
st=0;
dr=2*n+1;
int sum=0;
for(int i=1;i<=n;i++)
{
f>>X>>Y;
sum+=X;
a[st].push_back(i);
a[i].push_back(st);
a[dr].push_back(i+n);
a[i+n].push_back(dr);
d[st][i]=X;
d[i+n][dr]=Y;
}
g<<sum<<'\n';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
{
a[i].push_back(j+n);
a[j+n].push_back(i);
d[i][j+n]=1;
}
while(bfs())
{
for(int i=dr;i!=st;i=last[i])
{
flux[last[i]][i]++;
flux[i][last[i]]--;
}
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(flux[i][j]!=0)
g<<i<<" "<<j-n<<'\n';
return 0;
}