温州外贸网站建设公司,针对茅台酒企业网站建设方案,西安专业的网站优化,企业注册在哪个网站申请H - Holy Grail
题意#xff1a;
题干又臭又长 我简单说说 n个点#xff0c;m条有向边#xff0c;边权为负#xff0c;然后给你六组起始点#xff08;s点和t点#xff09;#xff0c;你要在s和t之间建一个有向边#xff0c;要使得权值最小#xff0c;问这六组边依次…H - Holy Grail
题意
题干又臭又长 我简单说说 n个点m条有向边边权为负然后给你六组起始点s点和t点你要在s和t之间建一个有向边要使得权值最小问这六组边依次是多少 不能形成负循环 可以添加负边题目给的边权也有可能为负
题解
既然可以添加负边那就是边权越小越好但是不能形成负循环想想我们要从s到t建一个边假如说t到s的最短路是w那我们能建的边就是-w这样两者抵消为0正好不是负循环这就是最佳情况 也就是我们从t开始跑最短路求到s的最短路径w然后我们添加的边权是-w. 注意这个w不一定是正的也有可能是负的为了不形成负循环我们就要添加正边权所以添加的边权取决于w的符号与w相反 这个题有好多注意的点
n个点点的序号是从0 ~ n-1 一开始我一直wa就是忘了第0点最短路记得跑spfa因为有负边权每次求出一组答案记得将答案更新到图中也就是建立s-t,边权为你求出的值因为后面的组有可能会用到这个边t组数据所以记得及时清零数组
代码
#includeiostream
#includecstdio
#includecstring
#includestring
#includequeue
const long long inf2147483647;
const int maxn10005;
const int maxm500005;
using namespace std;
int n,m,s,num_edge0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码不懂翻书看解释edge[num_edge].nexthead[from]; //链式存储下一条出边edge[num_edge].toto; //当前节点编号edge[num_edge].disdis; //本条边的距离head[from]num_edge; //记录下一次的出边情况
}
void spfa()
{queueint q; //spfa用队列这里用了STL的标准队列for(int i1; in; i) {dis[i]inf; //带权图初始化vis[i]0; //记录点i是否在队列中同dijkstra算法中的visited数组}q.push(s);dis[s]0;vis[s]1; //第一个顶点入队进行标记while(!q.empty()){int uq.front(); //取出队首q.pop();vis[u]0; //出队标记for(int ihead[u]; i; iedge[i].next) //邻接表遍历不多解释了也可用vector代替{int vedge[i].to; if(dis[v]dis[u]edge[i].dis) //如果有最短路就更改{dis[v]dis[u]edge[i].dis;if(vis[v]0) //未入队则入队{vis[v]1; //标记入队q.push(v);}}}}
}
int main()
{ios::sync_with_stdio(false);int t;cint;while(t--){memset(edge,0,sizeof(edge));memset(head,0,sizeof(head));num_edge0;cinnm;for(int i1; im; i){int u,v,w;cinuvw;if(u0)un;if(v0)vn;addedge(u,v,w);}for(int i1;i6;i){int u,v;cinuv;if(u0)un;if(v0)vn;sv;spfa(); //开始跑spfacout(-1)*dis[u]endl;addedge(u,v,(-1)*dis[u]);}}return 0;
}
