Pagini recente » Cod sursa (job #2544202) | Cod sursa (job #1432921) | Cod sursa (job #569537) | Cod sursa (job #2819370) | Cod sursa (job #1228602)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");
const int max_n = 105;
vector <int> a[2*max_n+1];
queue <int> q;
int Capacity[2*max_n+1][2*max_n+1],Flow[2*max_n+1][2*max_n+1],Max_Flow;
int start_node,end_node,out_degree,in_degree,P[2*max_n+1];
bool viz[2*max_n+1];
int i,j,n;
bool augmenting_path(const int &start_node, const int &end_node){
for(int i=0;i<=2*n+1;i++) viz[i]=0;
q.push(start_node);
viz[start_node]=1;
P[start_node]=start_node;
while(q.size())
{
int x=q.front();
q.pop();
if(x==end_node) continue;
for(int j=0;j<(int)a[x].size();j++)
{
int y=a[x][j];
if(!viz[y] && Capacity[x][y]>Flow[x][y]){
q.push(y);
viz[y]=1;
P[y]=x;
}
}
}
return viz[end_node];
}
int find_path_capacity_and_update(const int &start_node, const int &second_last, const int &end_node){
int path_capacity=Capacity[second_last][end_node]-Flow[second_last][end_node];
int y;
P[end_node]=second_last;
//find path_capacity
y=end_node;
while(y!=P[y]){
if(path_capacity>Capacity[P[y]][y]-Flow[P[y]][y])
path_capacity=Capacity[P[y]][y]-Flow[P[y]][y];
y=P[y];
}
//update
y=end_node;
while(y!=P[y]){
Flow[P[y]][y]+=path_capacity;
Flow[y][P[y]]-=path_capacity;
y=P[y];
}
return path_capacity;
}
int main(){
fi>>n; start_node=0; end_node=2*n+1;
for(i=1;i<=n;i++){
fi>>out_degree>>in_degree;
a[start_node].push_back(i);
a[i].push_back(start_node);
Capacity[start_node][i]=out_degree;
a[i+n].push_back(end_node);
a[end_node].push_back(i+n);
Capacity[i+n][end_node]=in_degree;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j){
a[j+n].push_back(i);
a[i].push_back(j+n);
Capacity[i][j+n]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) Flow[i][j]=0;
Max_Flow=0;
for(;augmenting_path(start_node,end_node);)
for(int j=0;j<(int)a[end_node].size();j++)
{
int y=a[end_node][j];
if(viz[y] && Capacity[y][end_node]>Flow[y][end_node])
{
int path_capacity=find_path_capacity_and_update(start_node,y,end_node);
Max_Flow+=path_capacity;
}
}
fo<<Max_Flow<<"\n";
for(i=1;i<=n;i++)
for(j=n;j<=2*n;j++)
if(Flow[i][j]>0) fo<<i<<" "<<j-n<<'\n';
fi.close();
fo.close();
return 0;
}