图论题：建图很重要！建图很重要！建图很重要！也是难点，因此要多加练习！！！
题意：
你需要到一个人（编号为1）那里买一个昂贵的东西，但你可以通过在其他人那里买别的东西来使它降价，其他人的东西也是这个道理，除此之外，每个人都有阶级，规定你不能在两个阶级差超过m的人那里买东西，最后问你买到这个东西所花费的最少价格
题解：
建图过程：先将你设置为0号节点，然后从0往每件物品连边，边权为这件物品的原始价格，每次输入替代品时，从该物品的替代品往该物品连边，边权为买了替代品后这件物品的优惠价格，这样这张图就建好了，如果没有阶级要求，那么答案就是从0到1的最短路
处理阶级问题：核心思想就是你最后必须要买到1号点的物品，因此1号点的阶级是核心，可以通过枚举在m范围内能到达1号点的阶级范围，每次枚举时跑一遍最短路，最后取这些最短路的最小值即可
AC代码：
code
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<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1<<30;
struct Edge{
int u,v,w,next;
}e[10005];
int n,m,cnt=0,head[10005],sta[10005],vis[10005];
int dis[10005];
inline void addedge(int u,int v,int w=0){
e[++cnt]=Edge{u,v,w,head[u]};
head[u]=cnt;
}
inline int spfa(int low,int high){
memset(dis,0x3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int> q;
vis[0]=1;
q.push(0);
dis[0]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(sta[v]<low||sta[v]>high) continue;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
return dis[1];
}
int main(){
scanf("%d%d",&m,&n);
int p,l,x,t,v;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&p,&l,&x);
addedge(0,i,p);
sta[i]=l;
for(int j=1;j<=x;++j){
scanf("%d%d",&t,&v);
addedge(t,i,v);
}
}
int ans=inf;
for(int i=sta[1]-m;i<=sta[1];++i){
ans=min(ans,spfa(i,i+m));
}
printf("%d\n",ans);
return 0;
}
|
题意
给出一张有向（有环）图，节点具有权值，若两点可达，则边权为$(终点-起点)^3$，给出若干次询问，每次询问两个点之间的最短路（如果<3或者不可达则输出“？”）
题解
注意了啊，这题他喵的有环！！！，而且权值可能为负！！！没跑了，一定是spfa跑负环的题，我们可以想到，所有能通过负环出去的节点都不可达（因为我在负环上已经可以无限次减小权值了），因此找到负环后dfs把负环所连的所有点全部设置为不可达就行了
后来发现，这题数据居然可以判完负环之后直接return回来（我寻思其他点也不一定更新完了啊？太水了）
AC代码（正常向）
code
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
inline ll read() {
ll kk=0,f=1;
char cc=getchar();
while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
return kk*f;
}
struct Edge{
int u,v,w,next;
}e[1000005];
int t,n,m,q,head[10005],cnt,vis[10005],ring[10005],reach[10005];
ll dis[10005],val[10005];
inline void addedge(int u,int v,int w=0){
e[++cnt]=Edge{u,v,w,head[u]};
head[u]=cnt;
}
void dfs(int x){
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(reach[v]==0) continue;
reach[v]=0;
dfs(v);
}
}
inline void spfa(){
memset(vis,0,sizeof(vis));
memset(ring,0,sizeof(ring));
memset(reach,1,sizeof(reach));
for(int i=1;i<=n;++i) dis[i]=inf;
queue<int> q;
vis[1]=1;
ring[1]=1;
dis[1]=0;
q.push(1);
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
if(reach[u]==0) continue;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
ll cha=val[v]-val[u];
if(dis[u]+cha*cha*cha<dis[v]){
dis[v]=dis[u]+cha*cha*cha;
ring[v]=ring[u]+1;
if(ring[v]>n){
dfs(v);
continue;
}
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
t=read();
int orz=0;
while(t--){
cnt=0;
memset(head,0,sizeof(head));
n=read();
for(int i=1;i<=n;++i) val[i]=read();
m=read();
int u,v;
for(int i=1;i<=m;++i){
u=read(),v=read();
addedge(u,v);
}
spfa();
q=read();
printf("Case %d:\n",++orz);
for(int i=1;i<=q;++i){
v=read();
if(dis[v]<3||dis[v]==inf||reach[v]==0){
printf("?\n");
}else{
printf("%lld\n",dis[v]);
}
}
}
return 0;
}
|
题意
你手上有x块钱，给一个无向图，从某个节点出发，你可以到别的节点那里换钱，换的钱是（x-C）*R，其中C是手续费，R是利率，且来回的手续费和利率不一定一样，问可否通过一波换钱回到出发点使得自己手上的钱增加？
题解
先考虑建图，每个节点除了存序号之外，还需要存一下手续费和利率
我们很容易想到，要使得此回路钱增加，不就是找一个正权环嘛，利用spfa找负环的思路，初始化所有距离为0，更新的时候取较大值更新，最后如果出现了能无限增大的环路就说明存在，否则不存在
AC代码
code
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
| #include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
struct Edge{
int u,v,next;
double R,C;
}e[1005];
int n,m,st,cnt,head[1005],vis[1005],ring[1005];
double dis[1005];
double sm;
inline void addedge(int u,int v,double R,double C){
e[++cnt]=Edge{u,v,head[u],R,C};
head[u]=cnt;
}
inline bool spfa(){
memset(dis,0,sizeof(dis));
vis[st]=1;
dis[st]=sm;
queue<int> q;
q.push(st);
ring[st]=1;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
double R=e[i].R,C=e[i].C;
if((dis[u]-C)*R>dis[v]){
dis[v]=(dis[u]-C)*R;
ring[v]=ring[u]+1;
if(ring[v]>n) return true;
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
return false;
}
int main(){
scanf("%d%d%d%lf",&n,&m,&st,&sm);
int x1,x2;
double rab,cab,rba,cba;
for(int i=1;i<=m;i++){
scanf("%d%d%lf%lf%lf%lf",&x1,&x2,&rab,&cab,&rba,&cba);
addedge(x1,x2,rab,cab);
addedge(x2,x1,rba,cba);
}
if(spfa()) printf("YES\n");
else printf("NO\n");
return 0;
}
|
题意
给你一个n*n的矩阵A，构造一个同维度的01矩阵B，满足
求最小的$\sum{A{ij}*B\{ij}}$
题解
这尼玛谁想得到是图论最短路的题？？？
首先我们可以考虑把原矩阵视为原图的邻接矩阵（第一行为起点1，最后一行为终点n），考虑题目的要求，对应了以下三条要求：
- 起点的出度为1
- 终点的入度为1
- 除了起点终点之外的点，出入度相同（可以为0）
那么题目就转化为了求一条从1到n的最短路
桥豆麻袋，中间节点出入度为零的情况呢？此时的答案应该是从起点到起点的一条环路和从终点到终点的一条环路的和，这个怎么求呢？？？
新姿势：SPFA求指定点的最小环
就起点来说，考虑初始将dis[1]设置为inf，然后把他的出边所连的点全部push进队列里，然后就正常跑一遍SPFA就行啦！（这样就能在跑spfa的时候把1到1的最短路也更新了，是不是很神奇？其实这就是在while循环之前自己先模拟一遍第一轮从起点连出边的更新过程罢了，这是为了满足1点在一开始不被更新的要求）好好想想就会明白，跑完spfa之后如果1点的dis更新了，那么这肯定是1点所连的最小环的权值和了，同理n点也一样，不再赘述
于是，这题的答案就是min(dis[1~n],minring[1]+minring[n])
AC代码
code
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
struct Edge{
int u,v,w,next;
}e[1000005];
int n,m,head[10005],cnt,vis[10005];
ll dis[10005];
inline void addedge(int u,int v,int w=0){
e[++cnt]=Edge{u,v,w,head[u]};
head[u]=cnt;
}
inline void spfa(int st){
memset(vis,0,sizeof(vis));
queue<int> q;
for(int i=1;i<=n;++i) dis[i]=inf;
for(int i=head[st];i;i=e[i].next){
if(e[i].v==st) continue;
vis[e[i].v]=1;
dis[e[i].v]=e[i].w;
q.push(e[i].v);
}
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
while(~scanf("%d",&n)){
cnt=0;
memset(head,0,sizeof(head));
int x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&x);
addedge(i,j,x);
}
}
spfa(1);
int ans=dis[n],d1=dis[1];
spfa(n);
int d2=dis[n];
printf("%d\n",min(ans,d1+d2));
}
return 0;
}
|
题意
有n头牛，给出若干对牛的相对等级，问有几头牛的等级排名是确定的？
题解
如果存在a>b且b>c，则一定有a>c，因此可以利用floyd的思想将牛之间的相对关系更新出来，如果排名可以确定的话，那么这头牛一定和其余n-1头牛存在关系，否则确定不出来
AC代码
code
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
| #include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
bool mm[125][125];
inline void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mm[i][k]&&mm[k][j]){
mm[i][j]=1;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
memset(mm,false,sizeof(mm));
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
mm[x][y]=true;
}
floyd();
int ans=0;
for(int i=1;i<=n;i++){
bool f=true;
for(int j=1;j<=n;j++){
if(i==j) continue;
if(!mm[i][j]&&!mm[j][i]){
f=false;
break;
}
}
if(f) ans++;
}
printf("%d\n",ans);
return 0;
}
|
题意
翻译过来就是：一张图，有若干正权双向道路和若干负权单向道路，问是否存在负权环？
题解
裸的spfa判负环，需要针对每个点都要判断一次，全部都没有才能算没有负环
AC代码
code
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
| #include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e8;
int n,m,k;
struct Edge{
int u,v,w,next;
}e[50005];
int cnt,head[555],vis[555],ring[555];
ll dis[555];
inline void addedge(int u,int v,int w=0){
e[++cnt]=Edge{u,v,w,head[u]};
head[u]=cnt;
}
inline bool spfa(int st){
memset(ring,0,sizeof(ring));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=inf;
queue<int> q;
dis[st]=0;
ring[st]=1;
vis[st]=1;
q.push(st);
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
ring[v]=ring[u]+1;
if(ring[v]>n) return true;
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
return false;
}
int main(){
int t;scanf("%d",&t);
while(t--){
cnt=0;
memset(head,0,sizeof(head));
scanf("%d%d%d",&n,&m,&k);
int u,v,w;
while(m--){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
while(k--){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,-w);
}
bool f=false;
for(int i=1;i<=n;i++){
if(f) break;
if(spfa(i)){
f=true;
}
}
if(!f) printf("NO\n");
else printf("YES\n");
}
return 0;
}
|
题意
翻译过来：一个有向图，问是否存在一条回路，这条回路上所有权值乘积大于1?
题解
利用spfa判负环的思想，初始化所有dis为1，然后判是否存在正权环即可
AC代码
code
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
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
int n,t;
struct Edge{
int u,v,next;
double w;
}e[4005];
int cnt,head[4005];
inline void addedge(int u,int v,double w){
e[++cnt]=Edge{u,v,head[u],w};
head[u]=cnt;
}
int vis[4005],ring[4005];
double dis[4005];
inline bool spfa(int st){
memset(vis,0,sizeof(vis));
memset(dis,1,sizeof(dis));
memset(ring,0,sizeof(ring));
queue<int> q;
vis[st]=1;
ring[st]=1;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
double w=e[i].w;
if(dis[v]<dis[u]*w){
dis[v]=dis[u]*w;
ring[v]=ring[u]+1;
if(ring[v]>n) return true;
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
int ccnt=0;
while(cin>>n&&n){
cnt=0;
memset(head,0,sizeof(head));
map<string,int> ma;
string s,ss;
for(int i=1;i<=n;i++){
cin>>s;
ma[s]=i;
}
cin>>t;
double giao;
for(int i=1;i<=t;i++){
cin>>s>>giao>>ss;
addedge(ma[s],ma[ss],giao);
}
cout<<"Case "<<++ccnt<<": ";
bool f=false;
for(int i=1;i<=n;i++){
if(f) break;
if(spfa(i)){
f=true;
}
}
if(f) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
|