「NOIP模拟赛」花园的守护之神
题目描述
看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，FZOI不相信眼泪，小bug与神兽们的战争将进行到底！
通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以在同一段小路上投掷多只小xie。每只小Xie可以拖延神兽一个单位的时间。即神兽通过整段路程的总时间，等于没有小xie时他们通过同样路径的时间加上路上经过的所有小路上的小xie数目总和。
神兽们是很聪明的。他们会在出发前侦查到每一段小路上的小Xie数目，然后选择总时间最短的路径。小Bug现在很想知道最少需要多少只小Xie，才能使得神兽从戈壁来到花园的时间变长。作为花园中可爱的花朵，你能帮助她吗?
输入格式
第1行包括一个整数N，表示地图中路点的个数；一个整数M，表示小路个数；以及整数S和T，分别表示戈壁和花园的路点编号。N个路点分别被编号为自然数1~N。
以下M行,每行三个整数A、B和C，表示路点A和B之间有一条小路相连，且通过它需要的时间为C。
输入数据保证两路点间最多只有一条小路相连，且戈壁和花园的路点是连通的。
输出格式
一个整数，表示使S到T之间最短路增长所需要的最少的小xie的数目。
输入样例
5 5 1 5
1 2 1
2 3 3
1 4 2
4 3 2
5 1
输出样例
1
数据范围
对于30%的数据，满足N≤10，M≤50。
对于50%的数据，满足N≤200，M≤10000。
对于全部的数据，满足N≤1000，M≤499500，0<C≤1000000。
题解
在最短路图中跑最大流（最小割）。。没了
|
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 100 101 102 103 104 |
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cstdlib> #include<cmath> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans; int n,m,S,T,cnt; int h[1005],q[1005],last[1005],last2[1005],d[1005]; bool mark[1005]; struct data{int from,to,next,v;}e[2000005],ed[2000005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].from=u;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].from=v;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void ins(int u,int v,int w) { ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=w; ed[++cnt].to=u;ed[cnt].next=last2[v];last2[v]=cnt;ed[cnt].v=0; } void dijkstra() { priority_queue<pa,vector<pa>,greater<pa> >q; for(int i=1;i<=n;i++)d[i]=1e60; memset(mark,0,sizeof(mark)); d[S]=0;q.push(make_pair(0,S)); while(!q.empty()) { int now=q.top().second;q.pop(); if(mark[now])continue;mark[now]=1; for(int i=last[now];i;i=e[i].next) if(d[now]+e[i].v<d[e[i].to]) { d[e[i].to]=d[now]+e[i].v; q.push(make_pair(d[e[i].to],e[i].to)); } } } void build() { int t=cnt;cnt=1; for(int i=1;i<=t;i++) if(d[e[i].from]+e[i].v==d[e[i].to]) ins(e[i].from,e[i].to,1); } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); h[S]=0;q[0]=S; while(head!=tail) { int now=q[head];head++; for(int i=last2[now];i;i=ed[i].next) if(ed[i].v&&h[ed[i].to]==-1) { h[ed[i].to]=h[now]+1; q[tail++]=ed[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last2[x];i;i=ed[i].next) if(h[x]+1==h[ed[i].to]) { w=f-used; w=dfs(ed[i].to,min(ed[i].v,w)); ed[i].v-=w;ed[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } int main() { n=read();m=read();S=read();T=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } dijkstra(); build(); while(bfs())ans+=dfs(S,inf); printf("%d\n",ans); return 0; } |
OI 课件=>
黄学长，请问输入样例最后一行为啥只有两个数啊？
那改成1 5 1咯
喔，谢谢。