Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## sss

Posted by Rose_max at 2016-01-21 16:17:50 on Problem 2112
```#include<cstdio>
#include<cstring>
using namespace std;
int map[300][300];
struct node
{
int x,y,c,next,other;
}a[2110000]; int len,last[1110000];
void ins(int x,int y,int c)
{
int k1,k2;
len++; k1=len;
a[len].x=x; a[len].y=y; a[len].c=c;
a[len].next=last[x]; last[x]=len;

len++; k2=len;
a[len].x=y; a[len].y=x; a[len].c=0;
a[len].next=last[y]; last[y]=len;

a[k1].other=k2;
a[k2].other=k1;
}
int h[1110000],list[1110000];
bool bt_h()
{
memset(h,0,sizeof(h)); h[st]=1;
{
for(int k=last[x]; k ; k=a[k].next)
{
int y=a[k].y;
if(a[k].c>0 && h[y]==0)
{
h[y]=h[x]+1;
list[tail++]=y;
}
}
}
if(h[ed]>0) return true;
return false;
}
int mymin(int x,int y){return x>y?y:x;}
int findflow(int x,int f)
{
if(x==ed) return f;
int s=0,t;
for(int k=last[x]; k ; k=a[k].next)
{
int y=a[k].y;
if(a[k].c>0 && h[y]==h[x]+1 && s<f)
{
s+=(t=findflow(y,mymin(a[k].c,f-s)));
a[k].c-=t; a[a[k].other].c+=t;
}
}
if(s==0) h[x]=0;
return s;
}int K,C,M;
int main()
{
scanf("%d%d%d",&K,&C,&M);
for(int i=1;i<=K+C;i++)
{
for(int j=1;j<=K+C;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==0)map[i][j]=999999999;
}
}
for(int k=1;k<=K+C;k++)
{
for(int i=1;i<=K+C;i++)
{
if(i!=k)
{
for(int j=1;j<=K+C;j++)
{
if(j!=k && i!=j)
{
if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];
}
}
}
}
}
int l=1,r=230*230,ans;
while(l<=r)
{
int mid=(l+r)/2;
int n=K+C;
len=0; memset(last,0,sizeof(last));
st=n+1; ed=n+2;
for(int i=1;i<=K;i++)
{
for(int j=K+1;j<=K+C;j++)
{
if(map[i][j]<=mid)ins(i,j,1);
}
}
for(int i=1;i<=K;i++)ins(st,i,M);
for(int i=K+1;i<=K+C;i++) ins(i,ed,1);
int s=0;
while(bt_h()==true)
{
int t=findflow(st,999999999);
while(t>0)
{
s+=t;
t=findflow(st,999999999);
}
}
if(s==C)
{
ans=mid; r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}```

Followed by: