Pagini recente » Cod sursa (job #668479) | Cod sursa (job #39762) | Cod sursa (job #2808565) | Cod sursa (job #332678) | Cod sursa (job #517051)
Cod sursa(job #517051)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
vector<int> st[105],dr[105];
vector<int> G[10005];
int out[105],in[105];
bool map[105][105];
int viz[10005],l[10006],r[10006],adev[10006],adev1[10006],S,n,N,D,d;
ofstream fout("harta.out");
bool dfs(int x)
{
if(viz[x]) return 0;
viz[x]=1;
vector<int>::iterator it;
for(it=G[x].begin();it<G[x].end();it++)
{
if(!l[*it])//&&!map[adev1[x]][adev[*it]])
{ map[adev1[x]][adev[*it]]=1;
l[*it]=x;
r[x]=*it;
return 1;
}
}
for(it=G[x].begin();it<G[x].end();it++)
{
if(dfs(l[*it]))//&&!map[adev1[x]][adev[*it]])
{ map[adev1[x]][adev[*it]]=1;
l[*it]=x;
r[x]=*it;
return 1;
}
}
return 0;
}
void solve()
{
int flow=0,ok=1, i;
while(ok)
{
ok=0;
for(i=1;i<=S;i++) viz[i]=0;
for(i=1;i<=S;i++)
if(!r[i])
if(dfs(i))
{
flow++;
ok=1;
}
}
fout<<flow+1<<"\n";
vector<int>::iterator it,jt;
for(i=1;i<=n;i++)
{ //////////
for(it=st[i].begin();it<st[i].end();it++)
{
if(r[*it])
{
fout<<i<<" "<<adev[r[*it]]<<"\n";
}
}
}
}
void cit()
{int x,y,i,ii,iii;
ifstream fin("harta.in");
fin>>n;
S=0;
D=0;
for(i=1;i<=n;i++)
{
fin>>x>>y;
for(ii=D+1;ii<=D+y;ii++)
adev[ii]=i;
D+=y;
out[i]=x;
in[i]=y;
}
for(i=1;i<=D;i++)
cout<<adev[i]<<" ";
d=0;
for(i=1;i<=n;i++)
{
d+=in[i];
for(ii=1;ii<=out[i];ii++)
{
S++;
st[i].pb(S);
adev1[S]=i;
for(iii=1;iii<=d-in[i];iii++)
{
G[S].pb(iii);
}
for(iii=d+1;iii<=D;iii++)
{
G[S].pb(iii);
}
}
}
vector<int>::iterator it,jt;
for(i=1;i<=n;i++)
{
cout<<i<<": ";
for(it=st[i].begin();it<st[i].end();it++)
{
for(jt=G[*it].begin();jt<G[*it].end();jt++)
{
cout<<adev[*jt]<<" ";
}
}
cout<<"\n";
}
fin.close();
}
int main()
{
cit();
solve();
fout.close();
return 0;
}