「网络流24题」航空计划

2014年4月3日3,4741

«问题描述：
给定一张航空图，图中顶点代表城市，边代表2城市间的直通航线。现要求找出一条满
足下述限制条件的且途经城市最多的旅行路线。
(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东
向西飞回起点(可途经若干城市)。
(2)除起点城市外，任何城市只能访问1次。
«编程任务：
对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。
«数据输入：
由文件airl.in提供输入数据。文件第1 行有2个正整数N 和V，N 表示城市数，N<100，
V 表示直飞航线数。接下来的N行中每一行是一个城市名，可乘飞机访问这些城市。城市名
出现的顺序是从西向东。也就是说，设i,j 是城市表列中城市出现的顺序，当i>j 时，表示
城市i 在城市j 的东边，而且不会有2 个城市在同一条经线上。城市名是一个长度不超过
15 的字符串，串中的字符可以是字母或阿拉伯数字。例如，AGR34或BEL4。
再接下来的V 行中，每行有2 个城市名，中间用空格隔开，如 city1 city2 表示city1
到city2 有一条直通航线，从city2 到city1 也有一条直通航线。
«结果输出:
程序运行结束时，将最佳航空旅行路线输出到文件airl.out 中。文件第1 行是旅行路
线中所访问的城市总数M。接下来的M＋1 行是旅行路线的城市名，每行写1 个城市名。首
先是出发城市名，然后按访问顺序列出其它城市名。注意，最后1行（终点城市）的城市名
必然是出发城市名。如果问题无解，则输出“No Solution!”。
输入文件示例输出文件示例
airl.in
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife

Edmonton Calgary

airl.out

7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

方案懒得写

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
string str[201];char ch[20];
string ans1[201];
int n,m,cnt=1,ans,num;
int from[201],head[201],q[201],dis[201];
bool inq[201];
struct data{int to,from,next,v,c;}e[100001];
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()
{
    memset(dis,-1,sizeof(dis));
    int t=0,w=1,i,now;
    dis[1]=0;inq[1]=1;q[0]=1;
    while(t!=w)
    {
        now=q[t];t++;if(t==201)t=0;
        for(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==201)w=0; 
                                     }
                }
        }
        inq[now]=0;
    }
    if(dis[n+n]==-1)return 0;return 1;
}
void mcf()
{
    int x=inf;
    for(int i=from[n+n];i;i=from[e[i].from])
    {
        x=min(e[i].v,x);
    }
    for(int i=from[n+n];i;i=from[e[i].from])
    {
        e[i].v-=x;e[i^1].v+=x;
        ans+=x*e[i].c;
    }
}
int find(char a[])
{
	for(int i=1;i<=n;i++)
	   if(str[i]==a)return i;
}
int main()
{
    //freopen("airl.in","r",stdin);
    //freopen("airl.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    	scanf("%s",ch);str[i]=ch;
    }
    insert(1,1+n,2,0);insert(n,n+n,2,0);
    for(int i=2;i<n;i++)insert(i,i+n,1,0);
    for(int i=1;i<=n;i++)
    {
    	int x,y;
    	scanf("%s",ch);x=find(ch);
    	scanf("%s",ch);y=find(ch);
    	insert(x+n,y,1,1);
    }
    while(spfa())mcf();
    if(e[2].v||e[4].v){printf("No Solution!");return 0;}
    printf("%d\n",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

using namespace std;

string str[201];char ch[20];

string ans1[201];

int n,m,cnt=1,ans,num;

int from[201],head[201],q[201],dis[201];

bool inq[201];

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

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()

{

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

int t=0,w=1,i,now;

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

while(t!=w)

{

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

for(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==201)w=0;

}

inq[now]=0;

}

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

}

void mcf()

{

int x=inf;

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

{

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

}

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

{

e[i].v-=x;e[i^1].v+=x;

ans+=x*e[i].c;

}

int find(char a[])

{

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

if(str[i]==a)return i;

}

int main()

{

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

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

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

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

{

scanf("%s",ch);str[i]=ch;

}

insert(1,1+n,2,0);insert(n,n+n,2,0);

for(int i=2;i<n;i++)insert(i,i+n,1,0);

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

{

int x,y;

scanf("%s",ch);x=find(ch);

scanf("%s",ch);y=find(ch);

insert(x+n,y,1,1);

}

while(spfa())mcf();

if(e[2].v||e[4].v){printf("No Solution!");return 0;}

printf("%d\n",ans);

return 0;

}

« 「BZOJ3171」[TJOI2013] 循环格「BZOJ2245」[SDOI2011] 工作安排 »

%%%hzwer orz orz

感觉不对啊黄学长，难道不应该是双向的边嘛，而且spfa出现环怎么破

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

「网络流24题」航空计划

分类目录

热门文章

Myfriends

近期评论