Pagini recente » Borderou de evaluare (job #2984356) | Cod sursa (job #916781) | Cod sursa (job #748004) | Cod sursa (job #20903) | Cod sursa (job #3181416)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
constexpr int nmax=300;
int fluxul[nmax][nmax];
int capacitati[nmax][nmax];
vector<int> graf[nmax];
int tata[nmax];
int nodePathCapacity[nmax];
ifstream cin("harta.in");
ofstream cout("harta.out");
void printMatrice(int* matrice,int size){
cout<<"============================================\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
cout<<matrice[i*size+j]<<" ";
}
cout<<"\n";
}
}
int bfs(int s,int t,int size){
nodePathCapacity[s]=__INT_MAX__;
for(int i=0;i<=size;i++){
tata[i]=-1;
}
tata[s]=-2;
queue<int> q;
q.push(s);
while (!q.empty())
{
int current=q.front();
q.pop();
for(int next:graf[current]){
if(tata[next]==-1&&capacitati[current][next]>fluxul[current][next]){
tata[next]=current;
nodePathCapacity[next]=min(nodePathCapacity[current],capacitati[current][next]-fluxul[current][next]);
if(next==t) return nodePathCapacity[next];
q.push(next);
}
}
}
return 0;
}
int main(){
int n;
cin>>n;
int muchii_totale=0;// imi trebuie cand afisez
int s=0;
int t=n+n+1;
for(int i=1;i<=n;i++){//pt fiecare oras
int x,y;
cin>>x>>y;
muchii_totale+=x;
for(int j=1;j<i;j++){//leg orasul i cu toate doar nu el
graf[i].push_back(j+n);
graf[j+n].push_back(i);
capacitati[i][j+n]=1;
}
for(int j=i+1;j<=n;j++){//la fel
graf[i].push_back(j+n);
graf[j+n].push_back(i);
capacitati[i][j+n]=1;
}
graf[s].push_back(i);
graf[i].push_back(s);
capacitati[s][i]=x;
graf[i+n].push_back(t);
graf[t].push_back(i+n);
capacitati[i+n][t]=y;
}
int flow_max=0;
while (1)
{
int flow=bfs(s,t,t);
//printMatrice(&fluxul[0][0],nmax);
if(flow==0) break;
flow_max+=flow;
int CurrentNode=t;
while (CurrentNode!=s)
{
int prev=tata[CurrentNode];
fluxul[prev][CurrentNode]+=flow;
fluxul[CurrentNode][prev]-=flow;
CurrentNode=prev;
}
}
cout<<muchii_totale<<'\n';
for(int i=1;i<=n;i++){
for(int j=n+1;j<t;j++){
if(fluxul[i][j]){
cout<<i<<" "<<j-n<<"\n";
}
}
}
return 0;
}