题目描述
每天早晨，FJ从家中穿过农场走到牛棚。农场由 N 块农田组成，农田通过 M 条双向道路连接，每条路有一定长度。FJ 的房子在 1 号田，牛棚在 N 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当FJ从一块田走到另一块时，总是以总路长最短的道路顺序来走。
FJ 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 M 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。
输入输出格式
输入格式：
第 1 行：两个整数 N, M。
第 2 到 M+1 行：第 i+1 行包含三个整数 A_i, B_i, L_i，A_i 和 B_i 表示道路 i 连接的田的编号，L_i 表示路长。
输出格式：
第 1 行：一个整数，表示通过使某条路加倍而得到的最大增量。
输入输出样例
说明
【样例说明】
若使 3 和 4 之间的道路长加倍，最短路将由 1-3-4-5 变为 1-3-5。
【数据规模和约定】
对于 30%的数据，N <= 70，M <= 1,500。
对于 100%的数据，1 <= N <= 100，1 <= M <= 5,000，1 <= L_i <= 1,000,000。
思路：其实思路很简单啦，那条线一定在最短路上，然后暴力就可以了。
╮(╯▽╰)╭还是懒啊！！枚举所有的边只能拿到90分啦。
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 5010 using namespace std; int n,m,num,ans,tot; int vis[MAXN],dis[MAXN]; int to[MAXN*2],net[MAXN*2],head[MAXN],cap[MAXN*2]; void add(int u,int v,int w){ to[tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot++; } void spfa(int now){ queue<int>que; memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); que.push(now);vis[now]=1;dis[now]=0; while(!que.empty()){ int now=que.front(); que.pop();vis[now]=0; for(int i=head[now];i!=-1;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ vis[to[i]]=1; que.push(to[i]); } } } } int main(){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } spfa(1);num=dis[n]; for(int i=0;i<tot;i+=2){ cap[i]=cap[i^1]=cap[i]*2; spfa(1);ans=max(ans,dis[n]-num); cap[i]=cap[i^1]=cap[i]/2; } cout<<ans; }
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 5010 using namespace std; int road[MAXN]; int n,m,num,ans,tot; int vis[MAXN],dis[MAXN],pre[MAXN*2],front[MAXN*2]; int to[MAXN*2],net[MAXN*2],head[MAXN],cap[MAXN*2]; void add(int u,int v,int w){ to[tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot++; } void spfa(int now){ queue<int>que; memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); que.push(now);vis[now]=1;dis[now]=0; while(!que.empty()){ int now=que.front(); que.pop();vis[now]=0; for(int i=head[now];i!=-1;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ pre[to[i]]=i;front[to[i]]=now; dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ vis[to[i]]=1; que.push(to[i]); } } } } int main(){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } spfa(1);num=dis[n]; int now=n,sum=0; while(now!=1){ road[++sum]=pre[now]; now=front[now]; } for(int i=1;i<=sum;i++){ cap[road[i]]*=2;cap[road[i]^1]*=2; spfa(1);ans=max(ans,dis[n]-num); cap[road[i]]/=2;cap[road[i]^1]/=2; } cout<<ans; }