首页 > 代码库 > BZOJ1266: [AHOI2006]上学路线route
BZOJ1266: [AHOI2006]上学路线route
1266: [AHOI2006]上学路线route
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 1273 Solved: 435
[Submit][Status]
Description
可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。 可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！” 合肥市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N) 两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。 [任务] 编写一个程序： ? 从输入文件中读取合肥市公交路线的信息； ? 计算出实际上可可和卡卡上学需要花费的最少时间； ? 帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的ci和最小；向输出文件输出答案。
Input
输入文件中第一行有两个正整数N和M，分别表示合肥市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第(i+1)行）用四个正整数描述第i条路线：pi, qi, ti, ci；具体含义见上文描述。
Output
输出文件最多有两行。 第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。 第二行输出一个整数C,表示Ci之和
Sample Input
6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
Sample Output
2
5
5
HINT
2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
合肥市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。
Source
题解：
第二问的做法比较炫酷。
把所有可以在最短路上的边拎出来，然后做一遍最小割，就OK了，这使得s到t没有一条完全有最短路组成的边，显然增大了s到t的最短路。
代码：不是WA就是T，我已经无语了。。。
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000 26 27 #define maxm 500000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 using namespace std; 44 45 inline int read() 46 47 { 48 49 int x=0,f=1;char ch=getchar(); 50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 54 55 return x*f; 56 57 } 58 int n,m,s,t,maxflow,tot=1,head[maxn],cur[maxn],h[maxn],q[maxm]; 59 int x[maxm],y[maxm],z[maxm],w[maxm],d[2][maxn]; 60 61 struct edge{int go,next,v;}e[2*maxm]; 62 bool v[maxn]; 63 64 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;} 65 66 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);} 67 68 bool bfs() 69 70 { 71 72 for(int i=s;i<=t;i++)h[i]=-1; 73 74 int l=0,r=1;q[1]=s;h[s]=0; 75 76 while(l<r) 77 78 { 79 80 int x=q[++l]; 81 82 for(int i=head[x];i;i=e[i].next) 83 84 if(e[i].v&&h[e[i].go]==-1) 85 86 { 87 88 h[e[i].go]=h[x]+1;q[++r]=e[i].go; 89 90 } 91 92 } 93 94 return h[t]!=-1; 95 96 } 97 98 int dfs(int x,int f) 99 100 {101 102 if(x==t) return f;103 104 int tmp,used=0;105 106 for(int i=head[x];i;i=e[i].next)107 108 if(e[i].v&&h[e[i].go]==h[x]+1)109 110 {111 112 tmp=dfs(e[i].go,min(e[i].v,f-used));113 114 e[i].v-=tmp;if(e[i].v)cur[x]=i;115 116 e[i^1].v+=tmp;used+=tmp;117 118 if(used==f)return f; 119 120 }121 122 if(!used) h[x]=-1;123 124 return used;125 126 }127 128 void dinic()129 130 {131 132 maxflow=0;133 134 while(bfs())135 136 {137 138 for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf);139 140 }141 142 }143 144 void spfa(int k)145 146 {147 148 for(int i=1;i<=n;++i) d[k][i]=inf;149 150 memset(v,0,sizeof(v));151 s=k==0?1:n;152 153 int l=0,r=1,x;q[1]=s;d[k][s]=0;154 155 while(l<r)156 157 {158 159 x=q[++l];v[x]=0;160 161 for(int i=head[x],y;i;i=e[i].next)162 163 if(d[k][x]+e[i].v<d[k][y=e[i].go])164 165 {166 167 d[k][y]=d[k][x]+e[i].v;168 169 170 if(!v[i]){v[i]=1;q[++r]=i;}171 172 }173 174 }175 176 }177 inline void ins2(int x,int y,int z)178 {179 e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;180 e[++tot].go=x;e[tot].v=z;e[tot].next=head[y];head[y]=tot;181 }182 int main()183 184 {185 freopen("input.txt","r",stdin);186 freopen("output.txt","w",stdout);187 n=read();m=read();188 for1(i,m)189 {190 x[i]=read();y[i]=read();z[i]=read();w[i]=read();191 ins2(x[i],y[i],z[i]);192 }193 spfa(0);spfa(1);194 tot=1;195 memset(head,0,sizeof(head));196 for1(i,m)197 {198 if(d[0][x[i]]+z[i]+d[1][y[i]]==d[0][n])insert(x[i],y[i],w[i]);199 if(d[0][y[i]]+z[i]+d[1][x[i]]==d[0][n])insert(y[i],x[i],w[i]);200 }201 s=0;t=n+1;202 insert(s,1,inf);insert(n,t,inf);203 dinic();204 printf("%d\n",d[0][n]);205 printf("%d\n",maxflow);206 207 return 0;208 209 }
无奈贴了标程
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define INF 2100000000 5 #define N 1005 6 #define M 250005 7 using namespace std; 8 struct arr{int go,c,next,s;}a[M]; 9 int map[N][N],dis[2][N],f[N],q[M*2],end[N];10 bool flag[N];11 int x,y,z,c,i,n,m,cnt,ans;12 void add(int u,int v,int s,int w)13 {14 a[++cnt].go=v;a[cnt].c=w;a[cnt].s=s;a[cnt].next=end[u];15 end[u]=cnt;16 }17 void SPFA(int o,int sta)18 {19 int h=0,t=1;q[1]=sta;20 memset(flag,0,sizeof(flag));21 dis[o][sta]=0;flag[sta]=true;22 while (h<t)23 {24 int now=q[++h];25 for (int i=end[now];i;i=a[i].next)26 {27 int go=a[i].go;28 if (dis[o][now]+a[i].s<dis[o][go])29 {30 dis[o][go]=dis[o][now]+a[i].s;31 if (!flag[go]) flag[go]=true,q[++t]=go;32 }33 }34 flag[now]=false;35 }36 } 37 void init()38 {39 for (int i=1;i<=n;i++)40 for (int j=end[i];j;j=a[j].next)41 if (dis[0][i]+a[j].s+dis[1][a[j].go]==dis[0][n])42 map[i][a[j].go]+=a[j].c;43 }44 bool bfs()45 {46 memset(f,-1,sizeof(f));47 int h=0,t=1;q[1]=1;f[1]=1;48 while (h<t)49 {50 int now=q[++h];if (now==n) return 1;51 for (int i=1;i<=n;i++)52 if (map[now][i]&&f[i]==-1)53 {54 f[i]=f[now]+1;55 q[++t]=i;56 }57 }58 return 0;59 }60 int dinic(int sta,int sum)61 {62 if (sta==n) return sum;int os=sum;63 for (int i=1;(i<=n)&&os;i++)64 if (map[sta][i]&&f[i]==f[sta]+1)65 {66 int Min=dinic(i,min(map[sta][i],os));67 map[sta][i]-=Min;map[i][sta]+=Min;os-=Min;68 }69 if (os==sum) f[sta]=-1;return sum-os;70 }71 int main()72 {73 scanf("%d%d",&n,&m);74 for (i=1;i<=m;i++)75 scanf("%d%d%d%d",&x,&y,&z,&c),add(x,y,z,c),add(y,x,z,c);76 memset(dis,60,sizeof(dis));SPFA(0,1);SPFA(1,n);77 ans=0;init();78 while (bfs())79 ans+=dinic(1,INF);80 printf("%d\n%d",dis[0][n],ans);81 return 0;82 }
挖坑，有空来看。。。
BZOJ1266: [AHOI2006]上学路线route
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。