BZOJ1266:上学路线route (最短路+最小割)
2024-08-30 17:14:32
可可和卡卡家住合肥市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学
的乘车路线不一定是最优的。 可可:“很可能我们在上学的路途上浪费了大量的时间,让我们写一个程序来计算上学需要的最少时间吧!” 合肥市一共设有N个公
交车站,不妨将它们编号为1…N的自然数,并认为可可和卡卡家住在1号汽车站附近,而他们学校在N号汽车站。市内有M条直达汽车路线,执行第i条路线的公交车
往返于站点pi和qi之间,从起点到终点需要花费的时间为ti。(<=i<=M, <=pi, qi<=N) 两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车
方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路
线i事实上都有一个代价ci:删去路线的ci越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小
。 [任务] 编写一个程序: 从输入文件中读取合肥市公交路线的信息; 计算出实际上可可和卡卡上学需要花费的最少时间; 帮助可可设计一个方案,
删除输入信息中的一些公交路线,使得删除后从家到学校需要的最少时间变大,而被删除路线的ci和最小;向输出文件输出答案。
Input
输入文件中第一行有两个正整数N和M,分别表示合肥市公交车站和公交汽车路线的个数。以下M行,每行(第i行,总第(i+)行)用四个正整数描述第i条路线:
pi, qi, ti, ci;具体含义见上文描述。
Output
输出文件最多有两行。 第一行中仅有一个整数,表示从可可和卡卡家到学校需要的最短时间。 第二行输出一个整数C,表示Ci之和
Sample Input Sample Output Hint
<=N<=, <=M<= , <=ti, ci<=
合肥市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为
上学需要的最短为正无穷大:这显然是一个合法的方案。
题意:从家(1)到学校(N),每条边有自己的长度和代价。现在需要删去一些边,使得最短路比原来大,求删去边的最小代价。
思路:把最短路上的边放入新图中,然后源点为1,汇点为N,求最小割即可。 数据小,时间多,暴力一点都无所谓。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
const int inf=;
int mp[][],c[][],N,M;
int Laxt[maxn],Next[maxn],To[maxn],cap[maxn],cnt=;
int add(int u,int v,int d){
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
cap[cnt]=d;
}
int vd[maxn],dis[maxn];
int sap(int u,int flow)
{
if(flow==||u==N) return flow;
int tmp,delta=;
for(int i=Laxt[u];i;i=Next[i]){
if(dis[u]==dis[To[i]]+&&cap[i]>){
tmp=sap(To[i],min(cap[i],flow-delta));
delta+=tmp;
cap[i]-=tmp;
cap[i^]+=tmp;
if(delta==flow||dis[]>N) return delta;
}
}
vd[dis[u]]--;
if(vd[dis[u]]==) dis[]=N+;
vd[++dis[u]]++;
return delta;
}
int u[maxn],v[maxn],x[maxn],y[maxn];
int main()
{
int i,j,k,ans=;
scanf("%d%d",&N,&M);
memset(mp,0x3f,sizeof(mp));
for(i=;i<=N;i++) mp[i][i]=;
for(i=;i<=M;i++){
scanf("%d%d%d%d",&u[i],&v[i],&x[i],&y[i]);
mp[u[i]][v[i]]=mp[v[i]][u[i]]=x[i];
c[u[i]][v[i]]=c[v[i]][u[i]]=y[i];
}
for(k=;k<=N;k++)
for(i=;i<=N;i++)
if(mp[i][k]!=0x3f)
for(j=;j<=N;j++)
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
for(i=;i<=M;i++){
if(mp[][u[i]]+x[i]+mp[v[i]][N]==mp[][N]){
add(u[i],v[i],y[i]);
add(v[i],u[i],);
}
if(mp[][v[i]]+x[i]+mp[u[i]][N]==mp[][N]){
add(v[i],u[i],y[i]);
add(u[i],v[i],);
}
}
printf("%d\n",mp[][N]);
while(dis[]<=N) ans+=sap(,inf);
printf("%d\n",ans);
return ;
}
最新文章
- mybatis中 ${}和#取值小记(Parameter index out of range)
- 有关define定义函数所注意的实例
- Ubuntu下使用SVN
- container的生命周期
- php 5.4 5.5 如何连接 ms sqlserver
- 分享一下一款直播App开发的过程
- redis 详解
- IIS Server is too busy 解决方法(IIS6)
- Delphi 把字符串读到流中的操作。
- 【转】morgan stanley 电面面经新鲜出炉
- Forms Authentication in ASP.NET MVC 4
- discuz 门户页模板中的keywords和description不能正常显示
- PPTP-VPN日志功能,记录用户登录时间,流量统计,IP地址等信息
- sqlserver 复制表结构(可以含有数据 或 只要表结构)
- vc++怎么可以直接刷掉MBR?搞笑的吧
- selenium笔记(1)
- leetcode《按递增顺序显示卡牌》
- <;TCP/IP>;DHCP动态主机配置协议
- 填写数独 洛谷P1784
- MySQL 创建用户并分配用户权限