题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1266
题意：一张无向图，边有时间，费用两个权值，第一问从 1 到 n 最短时间，第二问删除一些边使得最短时间变长的最小权值....
第一问随便最短路... 为了方便搞了个 floyd....
考虑第二问怎么搞... 其实是个萨博题... 却想了好半天.... 最短路变长只要旧最短路走不通就行了... 那么针对旧最短路建图，最小割，结束...
评论区说有重边... 实际上并没有，或者不需要处理.. 代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 510 #define M 124800 #define inf 210000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'|ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to,val; }edge[M<<1]; int cnt=2,head[M<<1]; void add(int from,int to,int val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void insert(int from,int to,int val) {add(from,to,val);add(to,from,0);} int n,m,f[N][N],ans,S,T; int a[M],b[M],c[M],d[M]; int dis[N]; queue<int> q; bool bfs() { memset(dis,0,sizeof(dis)); dis[S]=1,q.push(S); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(!dis[to]&&val) { dis[to]=dis[x]+1; q.push(to); } } } if(dis[T])return 1; return 0; } int dfs(int x,int v) { if(x==T||v==0)return v; int ret=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(dis[to]==dis[x]+1) { int f=dfs(to,min(v,val)); edge[i].val-=f,edge[i^1].val+=f; v-=f,ret+=f; if(v==0)break; } } if(ret==0)dis[x]=-1; return ret; } int main() { n=read(),m=read();S=1,T=n; memset(f,0x3f,sizeof(f)); for(int i=1;i<=m;i++) { a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read(); f[a[i]][b[i]]=f[b[i]][a[i]]=c[i]; } for(int i=1;i<=n;i++)f[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); printf("%d\n",f[1][n]); for(int i=1;i<=m;i++) { int x=a[i],y=b[i],z=c[i]; if(f[1][x]+f[y][n]+z==f[1][n]) insert(x,y,d[i]); if(f[1][y]+f[x][n]+z==f[1][n]) insert(y,x,d[i]); } while(bfs())ans+=dfs(S,inf); printf("%d",ans); } |
Comments | NOTHING