情之所至,甘之如饴

本题运用图论中的差分约束算法即可解决。差分约束需要连一些表示变量间大小关系的边,然后运用SPFA算法求解。

我们把顶点0作为“超级源点”,在主函数的开始首先执行下面一段代码。

1
for(int i=1;i<=n;i++) addEdge(n+1,i,0);

之后学网络流等知识还会遇到“超级汇点”。。。

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100100,maxm=500500;
struct Node
{
int v,c;
Node *next;
}*h[maxn],pool[maxm];
int tot=0;
int num[maxn];
int q[maxn],head=1,tail=1,vis[maxn],dis[maxm];
void addEdge(int u, int v, int c)
{
Node *p=&pool[++tot];
p->v=v; p->c=c; p->next=h[u]; h[u]=p;
}
int n,m,k,root;
int spfa()
{
root=n+1;
q[tail]=root;
tail++;
vis[root]=1;
for(int i=0;i<=n+1;i++) dis[i]=0x3f;
dis[root]=0;
while(head<tail)
{
if(tail>maxn) return 0;
k=q[head];
for(Node *p=h[k];p;p=p->next)
{
if(dis[p->v]>dis[k]+p->c)
{
dis[p->v]=dis[k]+p->c;
if(vis[p->v]==0)
{
q[tail]=p->v;
tail++;
vis[p->v]=1;
}
}
}
vis[q[head]]=0;
head++;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) addEdge(n+1,i,0);
for(int i=1;i<=m;i++){
int u,v,c,res;
scanf("%d",&res);
if(res==1){
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
}
else if(res==2){
scanf("%d%d%d",&u,&v,&c);
addEdge(v,u,-c);
}
else if(res==3){
scanf("%d%d",&u,&v);
addEdge(u,v,0);
}
}
if(spfa()==1) printf("Yes");
else printf("No");
return 0;
}

题面


德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号为1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。

给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入格式:


第一行: 4个由空格隔开的整数: T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出格式:


一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

题目分析


求单源最短路径的题目。俗话说得好,“图论一堆套模板”。以前觉得这只是调侃,现在渐渐接触到图论的内容了,感觉此话真的很有理。

求最短路有三种方法:Dijkstra,Floyd和SPFA,这里由于Bellman-Ford算法并不优于SPFA,就不算在里面了。考虑Floyd肯定会超时,Dijkstra又不能解决负权边的问题(尽管根据实际意义,没有那条道路会倒贴给过路人钱财的),果断SPFA。

代码分享


SPFA其实就是队列优化的Bellman-Ford算法。这里使用链式前向星来表示图。
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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=6210,maxm=400010;
struct Node
{
int v,c;
Node *next;
}*h[maxn],pool[maxm];
int tot=0;
int num[maxn];
int q[maxn],head,tail,vis[maxn],dis[maxm];
void addEdge(int u, int v, int c)
{
Node *p=&pool[++tot];
p->v=v; p->c=c; p->next=h[u]; h[u]=p;
}
int n,m,s;
inline bool spfa()
{
for(int i=1;i<=n;i++) dis[i]=2147483647;
vis[s]=1;
q[tail++]=s;
dis[s]=0;
while(head<tail)
{
int u=q[head++];
vis[u]=0;
for(Node *p=h[u];p;p=p->next)
{
if(dis[p->v]>dis[u]+p->c)
{
dis[p->v]=dis[u]+p->c;
if(vis[p->v]==0)
{
q[tail++]=p->v;
vis[p->v]=1;
num[p->v]++;
if(num[p->v]>n) return false;//存在负权回路
}
}
}
}
return true;//不存在负权回路
}
int Te;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&Te);
for(int i=1;i<=m;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
addEdge(v,u,c);
}
spfa();
printf("%d\n",dis[Te]);
return 0;
}

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
const int maxm=205*204/2, maxn=210;
int n,m,cur,time[maxn],dis[maxn][maxn];
//Floyd
int main(){
memset(dis,0x3f,sizeof(dis));
memset(time,0x3f,sizeof(time));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&time[i]);
dis[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
dis[u][v]=dis[v][u]=c;
}
int Q;
scanf("%d",&Q);
//跑Floyd
while(Q--)
{
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
while(time[cur]<=t)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dis[i][j]=min(dis[i][j],dis[i][cur]+dis[cur][j]);
cur++;
}
if(dis[x][y]==0x3f3f3f3f || time[x]>t || time[y]>t) printf("-1\n");
else printf("%d\n",dis[x][y]);
}
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k