图论
程序员文章站
2022-03-05 14:47:06
...
一、链式前向星
int head[n_max];
struct node
{
int to,next,w;
}edge[e_max];
int cnt=0;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
...
}其中to为边的终端，next为下一条边，w为边的权值，head[u]为以u为起点的最后一条边
二、割点
在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通
求SPF也就是求割点以及每个割点将系统分成几个连通分量
Trajan算法
选定一个根节点root进行DFS
对于根节点，如果有x>=2棵子树，则为割点，并将系统分割为x个连通分量
定义dfn[i]为节点i的DFS首次被访问时间，low[i]为i及i的子节点通过回边能够回溯到的最早的节点的dfn值，对于边e(u, v)，如果low[v]>=dfn[u]，则u点为割点
对于首次访问的节点i，有dfn[i]=low[i]=++num(num为访问次序累加数)，访问从i出发的所有边，e(i, j)中尚未被访问的点j执行dfs(j)，并不断更新low[i]=min(low[i]，low[j])，如果j已被访问即j不是i的子节点，一定有dfn[j]<dfn[i]，更新low[i]=min(low[i]，dfn[j])
②强联通分量
对于某一个联通分量S，如果S中任意一对点都可以相互到达，则称S为强联通分量
题目：HDU2767--- Proving Equivalences
三、生成树
①最小生成树
Kruskal算法(加边法)
首先把所有边按权值从小到大排列，将每个顶点看成一个独立的集合，然后从小到大选取边将两个顶点合成一个集合(使用并查集)，如果当前选的边的两个顶点属于同一个集合则放弃这个点(否则会形成环)，直到选出n-1条边为止
Prim算法(加点法)
从某一个顶点s开始，将s和剩下的点看成两个集合u和v，每次选取u到v权值最小的边，并将v中的这个顶点加入u，直到所有顶点属于同一个集合为止
②次小生成树
③最小度限制生成树
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int n_max=25;
const int inf=0x3f3f3f3f;
int g[n_max][n_max],p[n_max],m[n_max],link[n_max],cnt=1,ans=0,num=0,k;
bool tree[n_max][n_max];
map<string,int>vex;
struct node
{
int u,v,w;
node(int a=0,int b=0,int c=0):u(a),v(b),w(c)
{
}
bool operator<(const node& a)const
{
return w<a.w;
}
}dp[n_max];
vector<node>e;
int Min(int x,int y)
{
return x<y?x:y;
}
int Find(int x)
{
if(p[x]==x) return x;
return p[x]=Find(p[x]);
}
void unite(int x,int y)
{
x=Find(x);
y=Find(y);
p[x]=y;
}
bool same(int x,int y)
{
return Find(x)==Find(y);
}
void kruskal()
{
sort(e.begin(),e.end());
for(int i=0; i<e.size(); ++i)
{
int u=e[i].u,v=e[i].v;
if(u==1||v==1) continue;
if(!same(u,v))
{
ans+=e[i].w;
unite(u,v);
tree[u][v]=tree[v][u]=true;
}
}
}
void dfs(int cur,int pre)
{
for(int i=2; i<=cnt; ++i)
{
if(pre==i||!tree[cur][i]) continue;
if(dp[i].w==0)
{
if(dp[cur].w>g[cur][i]) dp[i]=dp[cur];
else
{
dp[i].u=cur;
dp[i].v=i;
dp[i].w=g[cur][i];
}
}
dfs(i,cur);
}
}
void solve()
{
for(int i=2; i<=cnt; ++i)
{
if(g[1][i]!=inf)
{
int pa=Find(i);
if(m[pa]>g[1][i])
{
m[pa]=g[1][i];
link[pa]=i;
}
}
}
for(int i=2; i<=cnt; ++i)
{
if(m[i]!=inf)
{
++num;
ans+=g[1][link[i]];
tree[1][link[i]]=tree[link[i]][1]=true;
}
}
for(int i=num+1; i<=k; ++i)
{
for(int j=2; j<=cnt; ++j)
{
if(tree[1][j])
dp[j].w=-inf;
}
dfs(1,-1);
int x,min_v=inf;
for(int j=2; j<=cnt; ++j)
{
if(min_v>g[j][1]-dp[j].w)
{
min_v=g[j][1]-dp[j].w;
x=j;
}
}
if(min_v>=0) break;
tree[1][x]=tree[x][1]=true;
int u=dp[x].u,v=dp[x].v;
tree[u][v]=tree[v][u]=false;
ans+=min_v;
}
}
int main()
{
int n,d;
string s1,s2;
cin>>n;
vex["Park"]=1;
for(int i=1; i<n_max; ++i)
p[i]=i;
memset(g,0x3f,sizeof(g));
memset(m,0x3f,sizeof(m));
for(int i=0; i<n; ++i)
{
cin>>s1>>s2>>d;
if(vex.find(s1)==vex.end()) vex[s1]=++cnt;
if(vex.find(s2)==vex.end()) vex[s2]=++cnt;
int u=vex[s1],v=vex[s2];
e.push_back(node(u,v,d));
g[u][v]=g[v][u]=Min(g[u][v],d);
}
cin>>k;
kruskal();
solve();
cout<<"Total miles driven: "<<ans<<endl;
return 0;
}④最优比率生成树
对于带权图G，其每条边i都包含两个值benefit[i]和cost[i]，要生成一棵 最小的树
所求比率r= ，x[i]=0 or 1，当r=
时，有
，对于任意r，如果r>=
，必定有
，用e[i]=
重新定义每一条边的权值，定义C(对于某个r，最小生成树权值和>=0)，进行二分搜索
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int n_max=1e3+5;
int n;
double x[n_max],y[n_max],z[n_max];
double ben[n_max][n_max],cost[n_max][n_max],dis[n_max][n_max],mincost[n_max];
bool vis[n_max];
double po(double t)
{
return t*t;
}
double Min(double x,double y)
{
return x<y?x:y;
}
bool prim(double x)
{
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
dis[i][j]=cost[i][j]-x*ben[i][j];
}
memset(mincost,0x7f,sizeof(mincost));
memset(vis,0,sizeof(vis));
mincost[1]=0;
double sum=0;
for(int i=1; i<=n; ++i)
{
int v=0;
for(int j=1; j<=n; ++j)
{
if(!vis[j]&&mincost[j]<mincost[v])
v=j;
}
vis[v]=true;
for(int j=1; j<=n; ++j)
if(!vis[j])
mincost[j]=Min(mincost[j],dis[v][j]);
}
for(int i=1;i<=n;++i)
sum+=mincost[i];
return sum>=0;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for(int i=1; i<=n; ++i)
scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
{
ben[i][j]=sqrt(po(x[i]-x[j])+po(y[i]-y[j]));
cost[i][j]=fabs(z[i]-z[j]);
}
}
double lb=0,ub=100;
while(ub-lb>0.00001)
{
double mid=(ub+lb)/2.0;
if(prim(mid)) lb=mid;
else ub=mid;
}
printf("%.3lf\n",lb);
}
return 0;
}四、二分图
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B)，则称图G为一个二分图
①最大匹配
在一个无向图中，找到一个边集S包含最多的边，使得这个边集覆盖到的所有顶点中的每个顶点只被一条边覆盖。S的大小即为最大匹配
匈牙利算法
枚举集合A中所有的点，试图在B中找到匹配，如果A中1与B中2有一条边相连，且2还没有找到匹配，则匹配成功，但如果2已经找到与A中3的匹配，则试图让3重新匹配；
②最小点覆盖
在一个无向图中，找到一个点集S包含最少的点，使得每条边至少有一个端点属于S。S的大小即为最小点覆盖
对于二分图，最小点覆盖=最大匹配
题目1：POJ1325---Machine Schedule
对于每一份工作，都会与A，B的其中一种模式相连，也就可以转化为A，B的模式相连，如果所有边都被覆盖证明工作也全部被完成，题目求的就是最小点覆盖，而且因为是二分图的关系，可以转化为求最大匹配数；注意，A，B初始状态为0能处理的工作都可以直接跳过
#include<cstdio>
#include<cstring>
using namespace std;
const int n_max=105;
bool g[n_max][n_max],vis[n_max];
int link[n_max],n,m,k;
bool match(int x)
{
for(int i=1;i<=m;++i)
{
if(!vis[i]&&g[x][i])
{
vis[i]=true;
if(!link[i]||match(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
scanf("%d%d",&m,&k);
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
int a,b,c;
for(int i=0;i<k;++i)
{
scanf("%d%d%d",&a,&b,&c);
if(b*c) g[b][c]=true;
}
int ans=0;
for(int i=1;i<=n;++i)
{
memset(vis,0,sizeof(vis));
if(match(i))
++ans;
}
printf("%d\n",ans);
}
return 0;
}将行i纳入集合A，列j纳入集合B，如果(i, j)处存在小行星，则作一条边e(i, j)，题目即可转化为求最小点覆盖，也就是求最大匹配
③最小路径覆盖
对于一个DAG图(有向无环图)找到路径集合S含有最少的路径，使得每一个顶点都只属于S中的其中一条路径，S的大小即为最小路径覆盖
DAG图的最小路径覆盖=DAG图节点数-对应二分图的最大匹配
定义每个订单包含出发时间和地址、结束时间和地址，设总共有x个订单，如果前面的订单j的结束时间加上从结束地址到当前订单i的出发地址耗费的时间再加1所得时间小于等于i出发时间则可以连一条从j到i的边，形成一个DAG图，接下来求出x-对应二分图的最大匹配，即为所求结果
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int n_max=505;
bool g[n_max][n_max],vis[n_max];
int link[n_max],m;
struct node
{
int a,b,c,d,s,e;
} point[n_max];
bool match(int x)
{
for(int i=1; i<=m; ++i)
{
if(!vis[i]&&g[x][i])
{
vis[i]=true;
if(!link[i]||match(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
int a,b;
for(int i=1; i<=m; ++i)
{
scanf("%d:%d",&a,&b);
scanf("%d%d%d%d",&point[i].a,&point[i].b,&point[i].c,&point[i].d);
point[i].s=a*60+b;
point[i].e=point[i].s+abs(point[i].a-point[i].c)+abs(point[i].b-point[i].d);
for(int j=i-1; j>=1; --j)
{
int x=abs(point[i].a-point[j].c)+abs(point[i].b-point[j].d)+1;
if(point[i].s>=x+point[j].e)
g[j][i]=true;
}
}
int ans=0;
for(int i=1; i<=m; ++i)
{
memset(vis,0,sizeof(vis));
if(match(i))
++ans;
}
printf("%d\n",m-ans);
}
return 0;
}
五、网络流
Dinic算法(最大增广路径)
定义dis[i]:起点到i的距离，可以看作结点i的层次，只保留每个点到下一个层次的弧，可以得到层次图
如图，建立层次图后，发现红色边为非有效边
阻塞流：不断寻找S->T的增广路径直至本层次图已经找不到路径为止
算法就是不断建立层次图，然后不断寻找增广路径的过程
struct edge
{
int to,cap;
edge(int a=0,int b=0)to(a),cao(b){}
}
vector<edge>edges;
vector<int>G[n_max];//G[i][j]存储节点i的第j条边在edges数组中的序号
int dis[n_max],cur[n_max],s,t,n,m,cnt;
bool bfs()
{
memeset(dis,-1,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<G[x].size();++i)
{
edge& e=edges[G[x][i]];
if(dis[e.to]==-1&&e.cap>0)
{
dis[e.to]=dis[x]+1;
q.push(e.to);
}
}
}
return dis[t]!=-1;
}
int dfs(int x,int f)
{
if(x==t||f==0) return f;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();++i)//使用引用，修改i的同时也修改了head[x]，从上次考虑的弧开始
{
edge& e=edge[G[x][i]];
if(dis[x]+1==dis[e.to]&&(temp=dfs(e.to,min(f,e.cap)))>0)
{
e.cap-=temp;
edges[G[x][i]^1].cap+=temp;
flow+=temp;
f-=temp;
if(f==0) break;
}
}
return flow;
}
int max_flow()
{
int flow=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
void add(int u,int v,int cap)
{
G[u].push_back(cnt++);//必须从0开始计数，否则不存在反向弧序数=正向弧序数^1
edges.push_back(edge(v,cap));
G[v].push_back(cnt++);
edges.push_back(edge(u,0));
}六、欧拉图
欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。
欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。
性质：对于无向连通图来说，度数为奇数的的点可以有2个(欧拉通路)或者0个(欧拉回路)，并且这两个奇点其中一个为起点另外一个为终点。
首先判断图是否为连通图，可以使用并查集，然后判断图奇度点个数是否满足0或2
根据异或自反性质：A XOR B XOR B = A，即对给定的数A，用同样的运算因子（B）作两次异或运算后仍得到A本身。可以知道一个点经过偶数次则对结果没有贡献，对于欧拉通路，一个点i如果不是起点或终点，很明显度degree[i]为偶数，并且经过的次数为degree[i]/2，而起点和终点则degree必定为奇数，且经过次数为(degree[i]+1)/2，而对于欧拉回路，每个点的度数都为偶数，且可以让任意点作为起点，且起点同时作为终点，还会额外再经过一次，因而必须枚举各个点作为终点的情况最后取最大值
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#define For(i,x,y) for(int i=x;i<=y;++i)
#define Fov(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
typedef long long ll;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
const int inf=0x3f3f3f3f;
const int n_max=1e5+5;
int degree[n_max],p[n_max],rak[n_max],a[n_max],n,m;
void init()
{
For(i,1,n)
{
p[i]=i;
degree[i]=0;
rak[i]=1;
}
}
int Find(int x)
{
if(p[x]==x) return x;
return p[x]=Find(p[x]);
}
void unite(int x,int y)
{
x=Find(x);
y=Find(y);
if(rak[x]>rak[y])
p[y]=x;
else
{
p[x]=y;
if(rak[x]==rak[y])
rak[y]++;
}
}
int main()
{
int T,u,v;
T=read();
while(T--)
{
init();
n=read(),m=read();
For(i,1,n)
a[i]=read();
For(i,1,m)
{
u=read();
v=read();
unite(u,v);
++degree[u];
++degree[v];
}
int x=Find(1),sum=0,flag=0,ans=0;
For(i,1,n)
{
if(degree[i]&1)
++sum;
if(x!=Find(i))
{
flag=1;
break;
}
}
if(sum!=0&&sum!=2)
flag=1;
if(flag)
{
printf("Impossible\n");
continue;
}
For(i,1,n)
{
if(degree[i]+1>>1&1)
ans^=a[i];
}
int temp=0;
if(sum==0)
{
For(i,1,n)
temp=max(temp,ans^a[i]);
ans=temp;
}
printf("%d\n",ans);
}
return 0;
}
注意，为了代码简洁，对所有情况都用了degree+1>>2&1，因为偶数+1再除2的值跟不加1没区别
七、k叉哈夫曼树
求K叉哈夫曼树，可以先将每条边的权值由小到大排列，放入队列q1，而把每次合成得到的边加入队列q2(q2明显也具有单调递增性)；对于每次选取k个子节点，很明显每一次都从两个队列队头元素中选较小的；注意，如果选取到最后发现选取的节点不足k个，很明显该方案并不是最优，因为原本一开始可以少选几个，而使得某些节点少加一次，并且最后还能恰好达到k合一，这才是最优的；对于这种情况的判定：每次选取k个再回1个，相当于每次去k-1个，而最后应该剩下1个，因而可以判定当(n-1)%(k-1)==0时一开始就选满k个时合理的，当不为0时，第一次应选(n-1)%(k-1)+1个，额外多选一个是为了补偿一开始合成回一个
题目求的就是满足条件的最小叉数，满足总花费随k增大而减小的规律，可使用二分法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#define For(i,x,y) for(int i=x;i<=y;++i)
#define Fov(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int n_max=1e5+5;
int w[n_max],n,mcost;
bool C(int k)
{
queue<int>q1,q2;
For(i,0,n-1)
q1.push(w[i]);
int rest=(n-1)%(k-1),ans=0;
if(rest!=0)
{
++rest;
For(i,1,rest)
{
ans+=q1.front();
q1.pop();
}
q2.push(ans);
}
while(1)
{
int temp=0,flag=0;
For(i,1,k)
{
if(q1.empty()&&q2.empty())
break;
if(q1.empty())
{
temp+=q2.front();
q2.pop();
continue;
}
if(q2.empty())
{
temp+=q1.front();
q1.pop();
continue;
}
int x1=q1.front(),x2=q2.front();
if(x1<x2)
{
temp+=x1;
q1.pop();
}
else
{
temp+=x2;
q2.pop();
}
}
ans+=temp;
if(q1.empty()&&q2.empty())
break;
q2.push(temp);
}
return ans>mcost;
}
int main()
{
int T=read();
while(T--)
{
n=read();
mcost=read();
For(i,0,n-1)
w[i]=read();
sort(w,w+n);
int lb=2,ub=n;
while(ub-lb>1)
{
int mid=(ub+lb)/2;
if(C(mid)) lb=mid;
else ub=mid;
}
printf("%d\n",ub);
}
return 0;
}八、最短路径
Floyd算法
Dijkstra算法
题目：ACM-ICPC 2018 南京赛区网络预赛L---Magical Girl Haze
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=x;i<=y;++i)
#define Fov(i,x,y) for(int i=x;i>=y;--i)
#define midf(a,b) ((a)+(b)>>1)
#define Num1(_) (_)<<1
#define Num2(_) ((_)<<1)|1
#define ss(_) scanf("%s",_)
#define si(_) scanf("%d",&_)
#define sii(x,y) scanf("%d%d",&x,&y)
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
inline int read()
{
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const ll inf=1e18;
const double pi=acos(-1.0);
const int n_max=1e5+10;
int head[n_max],cnt,n,m,k;
bool vis[n_max][15];
ll dis[n_max][15];
struct node
{
int to,nex;
ll w;
}e[n_max<<1];
struct point
{
ll d;
int u,x;
bool operator<(const point& a)const
{
return d>a.d;
}
point(ll a=0,int b=0,int c=0):d(a),u(b),x(c){}
};
void add(int u,int v,ll w)
{
e[++cnt].to=v;
e[cnt].nex=head[u];
e[cnt].w=w;
head[u]=cnt;
}
void dijkstra(int s)
{
For(i,1,n)
For(j,0,k)
vis[i][j]=false,dis[i][j]=inf;
priority_queue<point>q;
q.push(point(0,s,0));
dis[s][0]=0;
while(!q.empty())
{
point p=q.top();q.pop();
int u=p.u,x=p.x;
if(vis[u][x]) continue;
vis[u][x]=true;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].to;
if(!vis[v][x]&&dis[v][x]>dis[u][x]+e[i].w)
{
dis[v][x]=dis[u][x]+e[i].w;
q.push(point(dis[v][x],v,x));
}
if(x<k&&!vis[v][x+1]&&dis[v][x+1]>dis[u][x])
{
dis[v][x+1]=dis[u][x];
q.push(point(dis[v][x+1],v,x+1));
}
}
}
}
int main()
{
int T,u,v;
ll w;
si(T);
while(T--)
{
siii(n,m,k);
cnt=0;
For(i,1,n) head[i]=0;
For(i,1,m)
{
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
dijkstra(1);
printf("%lld\n",dis[n][k]);
}
return 0;
}
SPFA算法
第K短路径
题目：ACM-ICPC 2018 沈阳赛区网络预赛D---Made In Heaven
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define Fov(i,x,y) for(int i=(x);i>=(y);--i)
#define Fo(i,x,y) for(int i=(x);i<(y);++i)
#define midf(a,b) ((a)+(b)>>1)
#define L p<<1
#define R (p<<1)|1
#define ss(_) scanf("%s",_)
#define si(_) scanf("%d",&_)
#define sii(x,y) scanf("%d%d",&x,&y)
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
inline int read()
{
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int n_max=1e3+10;
struct node
{
int to,w,nex;
}re[n_max*10],e[n_max*10];
struct ast
{
int f,g,x;
ast(int a=0,int b=0,int c=0):f(a),g(b),x(c) {}
bool operator<(const ast& a)const
{
if(f==a.f) return g>a.g;
return f>a.f;
}
};
int head[n_max],rhead[n_max],dis[n_max],cnt;
bool vis[n_max];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
re[cnt].to=u;
re[cnt].w=w;
re[cnt].nex=rhead[v];
rhead[v]=cnt;
}
void spfa(int s)
{
queue<int >q;
mem(dis,0x3f);
q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=false;
for(int i=rhead[u];i;i=re[i].nex)
{
int v=re[i].to;
if(dis[v]>dis[u]+re[i].w)
{
dis[v]=dis[u]+re[i].w;
if(!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
}
}
int astar(int s,int t,int k)
{
if(dis[s]==inf) return inf;
if(s==t) ++k;
priority_queue<ast>q;
q.push(ast(dis[s],0,s));
int tot=0;
ast p,u;
while(!q.empty())
{
u=q.top();q.pop();
if(u.x==t)
{
++tot;
if(tot==k) return u.g;
}
for(int i=head[u.x];i;i=e[i].nex)
{
p.x=e[i].to;
p.g=u.g+e[i].w;
p.f=p.g+dis[p.x];
q.push(p);
}
}
return inf;
}
int main()
{
int S,E,K,T,n,m;
while(~sii(n,m))
{
scanf("%d%d%d%d",&S,&E,&K,&T);
mem(head,0);
mem(rhead,0);
int u,v,w;
cnt=0;
For(i,1,m)
{
siii(u,v,w);
add(u,v,w);
}
spfa(E);
int ans=astar(S,E,K);
if(ans<=T) printf("yareyaredawa\n");
else printf("Whitesnake!\n");
}
return 0;
}
下一篇： C# 利用委托进行异步处理实例代码