「BZOJ2055」80人环游世界

2014年6月17日4,6820

Description

Input

第一行两个正整数N，M。第二行有N个不大于M正整数，分别表示V1，V2……VN。接下来有N ¡ 1行。第i行有N ¡ i个整数，该行的第j个数表示从第i个国家到第i + j个国家的机票费（如果该值等于¡1则表示这两个国家间没有通航）。

Output

在第一行输出最少的总费用。

Sample Input

6 3
2 1 3 1 2 1
2 6 8 5 0
8 2 4 1
6 1 0
4 -1
4

Sample Output

HINT

1<= N < =100 1<= M <= 79

题解

m个人的起始点任意。。。

这什么奇怪的设定。。

知道这个以后随便写个上下界费用流就差不多了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
#define ll long long
#define S 201
#define T 202
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt=1,ans;
int head[205],in[205],q[205],dis[205],from[205];
bool inq[205];
struct data{int to,from,next,v,c;}e[500005];
void ins(int u,int v,int w,int c)
{
    e[++cnt].to=v;e[cnt].from=u;
    e[cnt].next=head[u];head[u]=cnt;
    e[cnt].v=w;e[cnt].c=c;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
    for(int i=0;i<=T;i++)dis[i]=inf;
    int t=0,w=1;
    dis[0]=0;q[0]=0;inq[0]=1;
    while(t!=w)
    {
        int now=q[t];t++;if(t==205)t=0;
        for(int i=head[now];i;i=e[i].next)
            if(e[i].v&&e[i].c+dis[now]<dis[e[i].to])
            {
                dis[e[i].to]=e[i].c+dis[now];
                from[e[i].to]=i;
                if(!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    q[w++]=e[i].to;
                    if(w==205)w=0;
                }
            }
        inq[now]=0;
    }
    if(dis[T]==inf)return 0;
    return 1;
}
void dfs()
{
    int x=inf;
    for(int i=from[T];i;i=from[e[i].from])
        x=min(e[i].v,x);
    for(int i=from[T];i;i=from[e[i].from])
        {ans+=x*e[i].c;e[i].v-=x;e[i^1].v+=x;}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		insert(i,i+n,0,0);
		in[i]-=x;in[i+n]+=x;
	}
	insert(0,S,m,0);
	for(int i=1;i<=n;i++)
	    insert(S,i,inf,0);
	for(int i=1;i<=n;i++)
	   for(int j=i+1;j<=n;j++)
	   {
	   	   int x=read();
	   	   if(x!=-1)insert(i+n,j,inf,x);
	   }
	for(int i=1;i<=2*n;i++)
	    if(in[i]>0)insert(0,i,in[i],0);
	    else insert(i,T,-in[i],0);
	while(spfa())dfs();
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#define inf 0x7fffffff

#define ll long long

#define S 201

#define T 202

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt=1,ans;

int head[205],in[205],q[205],dis[205],from[205];

bool inq[205];

struct data{int to,from,next,v,c;}e[500005];

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

{

e[++cnt].to=v;e[cnt].from=u;

e[cnt].next=head[u];head[u]=cnt;

e[cnt].v=w;e[cnt].c=c;

}

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

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

bool spfa()

{

for(int i=0;i<=T;i++)dis[i]=inf;

int t=0,w=1;

dis[0]=0;q[0]=0;inq[0]=1;

while(t!=w)

{

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

for(int i=head[now];i;i=e[i].next)

if(e[i].v&&e[i].c+dis[now]<dis[e[i].to])

{

dis[e[i].to]=e[i].c+dis[now];

from[e[i].to]=i;

if(!inq[e[i].to])

{

inq[e[i].to]=1;

q[w++]=e[i].to;

if(w==205)w=0;

}

inq[now]=0;

}

if(dis[T]==inf)return 0;

return 1;

}

void dfs()

{

int x=inf;

for(int i=from[T];i;i=from[e[i].from])

x=min(e[i].v,x);

for(int i=from[T];i;i=from[e[i].from])

{ans+=x*e[i].c;e[i].v-=x;e[i^1].v+=x;}

}

int main()

{

n=read();m=read();

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

{

int x=read();

insert(i,i+n,0,0);

in[i]-=x;in[i+n]+=x;

}

insert(0,S,m,0);

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

insert(S,i,inf,0);

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

for(int j=i+1;j<=n;j++)

{

int x=read();

if(x!=-1)insert(i+n,j,inf,x);

}

for(int i=1;i<=2*n;i++)

if(in[i]>0)insert(0,i,in[i],0);

else insert(i,T,-in[i],0);

while(spfa())dfs();

printf("%d",ans);

return 0;

}

« 「POJ2396」Budget 「BZOJ2502」清理雪道 »

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

「BZOJ2055」80人环游世界

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论