「th04」河城荷取

2014年3月23日4,5650

Description

在幻想乡，河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外，还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大，所以为它充能是一件很麻烦的事。人形一共有N个电能池，编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口，而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道，每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个值时，所以激活代价小于等于这个值的管道都会被激活，但是每一条管道只能够最多传送limit个单位的电能。外部接口到电能池和电能池到动力炉核心的管道传输没有限制并且激活代价为0。现在荷取想往动力炉核心输入至少K个单位的电能，求需要的最小激活度。

Input

第1行：4个正整数N,M,L, K
第2..M+1行：4个整数，u,v,limit,cost，表示一条由u到v的管道，传输极限limit，激活代价为cost

Output

第1行：1个整数，表示最小激活代价

Sample Input

6 5 3 3

1 4 2 4

2 4 3 5

3 5 4 2

4 6 2 3

5 6 3 4

Sample Output

4

Hint

对于30%的数据： 1 ≤ L ≤ N ≤ 100 ，0 ≤ M ≤ 2,000 ，1 ≤ cost ≤ 10,000
对于60%的数据： 1 ≤ L ≤ N ≤ 1,000，0 ≤ M ≤ 20,000 ，1 ≤ cost ≤ 10,000
对于100%的数据：1 ≤ L ≤ N ≤ 2,000，0 ≤ M ≤ 80,000 ，1 ≤ cost ≤ 1,000,000
对于100%的数据：1 ≤ limit ≤ 1,000

保证任意(u,v)都只出现一次

题解

二分答案 + 最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
int ans,cnt,mn;
int n,m,l,k;
int head[2005],h[2005];
int u[80001],v[80001],limit[80001],c[80001];
struct data{int to,next,v;}e[300001];
void ins(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs()
{
     int q[2005],t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     q[0]=h[0]=0;
     while(t!=w)
     {
            now=q[t];t++;if(t==2001)t=0;
            i=head[now];
            while(i)
            {
                  if(e[i].v&&h[e[i].to]<0)
						{h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==2001)w=0;}
                  i=e[i].next;
             }
     }
     if(h[n+1]==-1)return 0;
     return 1;
     }
int dfs(int x,int f)
{
    if(x==n+1)return f;
    int i=head[x],w,used=0;
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                w=f-used;
                w=dfs(e[i].to,min(w,e[i].v));   
                e[i].v-=w;
                e[i^1].v+=w;
                used+=w;
                if(used==f)return f;                      
                }
                i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
    }
void dinic(){while(bfs())ans+=dfs(0,inf);}
void build(int x)
{
	memset(head,0,sizeof(head));
	cnt=1;for(int i=1;i<=l;i++)insert(0,i,inf);
	for(int i=1;i<=m;i++)
		if(x>=c[i])insert(u[i],v[i],limit[i]);
	insert(n,n+1,inf);
}
int main()
{
	 //freopen("nitori.in","r",stdin);
	 //freopen("nitori.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&l,&k);
    for(int i=1;i<=m;i++)
    	  scanf("%d%d%d%d",&u[i],&v[i],&limit[i],&c[i]);
    int l=0,r=1000000;
    while(l<=r)
    {
    	  int mid=(l+r)>>1;
    	  ans=0;build(mid);dinic();
    	  if(ans>=k)
    	  {
    	  	   mn=mid;
    	  	   r=mid-1;
    	  }
    	  else l=mid+1;
    }
    printf("%d",mn);
    return 0; 
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

using namespace std;

int ans,cnt,mn;

int n,m,l,k;

int head[2005],h[2005];

int u[80001],v[80001],limit[80001],c[80001];

struct data{int to,next,v;}e[300001];

void ins(int u,int v,int w)

{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,0);}

bool bfs()

{

int q[2005],t=0,w=1,i,now;

memset(h,-1,sizeof(h));

q[0]=h[0]=0;

while(t!=w)

{

now=q[t];t++;if(t==2001)t=0;

i=head[now];

while(i)

{

if(e[i].v&&h[e[i].to]<0)

{h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==2001)w=0;}

i=e[i].next;

}

if(h[n+1]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==n+1)return f;

int i=head[x],w,used=0;

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans+=dfs(0,inf);}

void build(int x)

{

memset(head,0,sizeof(head));

cnt=1;for(int i=1;i<=l;i++)insert(0,i,inf);

for(int i=1;i<=m;i++)

if(x>=c[i])insert(u[i],v[i],limit[i]);

insert(n,n+1,inf);

}

int main()

{

//freopen("nitori.in","r",stdin);

//freopen("nitori.out","w",stdout);

scanf("%d%d%d%d",&n,&m,&l,&k);

for(int i=1;i<=m;i++)

scanf("%d%d%d%d",&u[i],&v[i],&limit[i],&c[i]);

int l=0,r=1000000;

while(l<=r)

{

int mid=(l+r)>>1;

ans=0;build(mid);dinic();

if(ans>=k)

{

mn=mid;

r=mid-1;

}

else l=mid+1;

}

printf("%d",mn);

return 0;

}

« 「BZOJ1305」[CQOI2009] dance跳舞「JoyOI1431」分配任务 »

hzwer.com _ Home | http://hzwer.com

「th04」河城荷取

分类目录

热门文章

Myfriends

近期评论