牛客練習試合43(ネットフロー)
3222 ワード
リンク:https://ac.nowcoder.com/acm/contest/548/E出典:牛客網の構想:源点S終点Tを創立して、各都市を2つの点と見なして、例えばi番目の都市はi番目とi+1番目の点に分けることができて、S->iはi番目の都市の排水量で、i+n->Tはi番目の都市の1日の清潔な水量です
#include
using namespace std;
using LL=long long;
const LL inf=0x3f3f3f3f3f3f3f3f;
const int up=1e9;
const int maxn=405;
const int M=162000;
int head[maxn],nxt[M],to[M],w[M],tot=-1;
int S,T;
int n,m;
int sum;
void add(int u,int v,int we)
{
tot++;
nxt[tot]=head[u];
head[u]=tot;
to[tot]=v;
w[tot]=we;
}
void add_edge(int u,int v,int we)
{
add(u,v,we);
add(v,u,0);
}
LL cost[maxn][maxn];
struct node
{
int x,y;
}a[M/4];
int cur[maxn],dep[maxn];
queueq;
bool bfs()
{
memset(dep,0,sizeof(dep));
while(q.size())
q.pop();
dep[S]=1;
q.push(S);
int u;
while(q.size())
{
u=q.front();
q.pop();
for(int i=head[u];~i;i=nxt[i])
{
if(dep[to[i]]==0&&w[i]>0)
{
dep[to[i]]=dep[u]+1;
q.push(to[i]);
}
}
}
if(dep[T])
return 1;
return 0;
}
int dfs(int u,int dist)
{
if(u==T||dist==0)
return dist;
for(int &i=cur[u];~i;i=nxt[i])
{
if(dep[to[i]]==dep[u]+1&&w[i]>0)
{
int d=dfs(to[i],min(dist,w[i]));
if(d>0)
{
w[i]-=d;
w[i^1]+=d;
return d;
}
}
}
return 0;
}
int dinic()
{
int ans=0;
while(bfs())
{
for(int i=0;i<=2*n+1;i++)
cur[i]=head[i];
while(int d=dfs(S,up))
{
ans+=d;
}
}
return ans;
}
bool check(LL now)
{
memset(head,-1,sizeof(head));
tot=-1;
int i,j;
for(i=1;i<=n;i++)
{
add_edge(S,i,a[i].x);
add_edge(i+n,T,a[i].y);
add_edge(i,i+n,up);
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(cost[i][j]<=now)
{
add_edge(i,j+n,up);
add_edge(j,i+n,up);
}
}
if(dinic()>=sum)
return 1;
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
int i,j,k;
S=0,T=2*n+1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
sum+=a[i].x;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=inf;
for(i=1;i<=n;i++)
cost[i][i]=0;
LL val;
for(i=0;icost[i][k]+cost[k][j])
{
cost[i][j]=cost[i][k]+cost[k][j];
r=max(r,cost[i][j]);
}
}
while(l<=r)
{
mid=l+r>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%lld
",ans);
return 0;