提供网站建设哪家好,企业163邮箱登录入口,北京企业名录一览表,重庆那些公司的网站是网易做的题干#xff1a; 题目大意#xff1a;
一个有向图#xff0c;编号1~n的n个点#xff0c;m条边#xff0c;规定1为起点#xff0c;2为终点#xff0c;问对于每一条边#xff0c;反转它的方向#xff0c;最短路会不会发生改变#xff0c;如果变短了#xff0c;输出HA…题干 题目大意
一个有向图编号1~n的n个点m条边规定1为起点2为终点问对于每一条边反转它的方向最短路会不会发生改变如果变短了输出HAPPY变长了或者到达不了了输出SAD不变的话输出SOSO。
解题报告
建三个图正向图G1反向图G2对于G1的边(u,v)假如G1.d[u]G2.[v]wG1.d[2]那么他就是最短路上的一条路径用这些路径重新建一个图G3那么显然这个G3中任意一条点1到点2的路径都是最短路对G3跑一遍tarjan求个桥标记处理一下对应G1的哪条边记下编号。然后枚举G1的每一条边如果G1.d[v]G2.[u]wG1.d[2]那么就是HAPPY否则分两种情况如果这条边是桥那么改变它的方向是会改变新图的连通性的必定不能到达2点输出SAD如果不是桥那么就是SOSO因为有别的方式可以到达点2。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
struct Edge {int fr,to;ll w;int ne;
// Edge(int fr0,int to0,ll w0,int ne-1):fr(fr)
};
struct Graph {struct Point {int pos;ll c;Point(){}Point(int pos,ll c):pos(pos),c(c){}bool operator(const Point b) const {return c b.c;}};Edge e[MAX];int tot 0;//总共tot条边编号0~(tot-1) int head[MAX],id[MAX];bool vis[MAX];ll d[MAX];void add(int u,int v,ll w) {e[tot].fr u;e[tot].to v;e[tot].ne head[u];e[tot].w w;head[u] tot; }void Dijkstra(int st) {priority_queuePoint pq;memset(d,0x3f,sizeof d);memset(vis,0,sizeof vis);d[st] 0;pq.push(Point(st,0));while(pq.size()) {Point cur pq.top();pq.pop();if(vis[cur.pos]) continue;vis[cur.pos] 1; for(int i head[cur.pos]; ~i; i e[i].ne) {if(d[e[i].to] d[cur.pos] e[i].w) {d[e[i].to] d[cur.pos] e[i].w;pq.push(Point(e[i].to,d[e[i].to]));}}}}///int clk 0;int DFN[MAX],LOW[MAX],bi[MAX];void id_add(int u,int v,ll w,int _id) {e[tot].fr u;e[tot].to v;e[tot].ne head[u];e[tot].w w;id[tot] _id;//记录编号为tot的这条边是第几个点的 head[u] tot; }void tarjan(int x,int rt) {DFN[x] LOW[x] clk;for(int i head[x]; ~i; i e[i].ne) {if(e[i].to rt) continue; if(!DFN[e[i].to]) {tarjan(e[i].to,x);LOW[x] min(LOW[x],LOW[e[i].to]);if(LOW[e[i].to] DFN[x]) {
// printf(%d**%d\n,e[i].fr,e[i].to);bi[id[i]] 1;}}else LOW[x] min(LOW[x],DFN[e[i].to]);
//或者不用判重边了直接用这一句
// else if(e[i].to ! rt)LOW[x] min(LOW[x],DFN[e[i].to]);
//而且其实不应该是直接用这一句 而应该是传参的时候传入边的编号rt这样我们else if(i ! (rt^1))这样才对因为这代表的才是不是祖先边的回边。所以这里严格来说不能直接判断是否是祖先节点因为还有可能有重边或者自环的情况但是这题因为数据保证了所以无所谓。 }}void init() {tot 0;clk 0;memset(head,-1,sizeof head);}
} G1,G2,G3;
int main()
{int n,m;int u,v;ll w;cinnm;G1.init();G2.init();G3.init();//G1是原图G2是反图G3是最短路无向子图 for(int i 1; im; i) {scanf(%d%d%lld,u,v,w);G1.add(u,v,w);G2.add(v,u,w);//加反边 }G1.Dijkstra(1);G2.Dijkstra(2);ll DIS G1.d[2];
//构造G3这个最短路子图。 for(int i 0; iG1.tot; i) {u G1.e[i].fr;v G1.e[i].to;w G1.e[i].w;if(G1.d[u] G2.d[v] w DIS) {
// printf(%d%d\n,u,v);G3.id_add(u,v,w,i);G3.id_add(v,u,w,i);}}G3.tarjan(1,-1);//改成0也可以过。for(int i 0; iG1.tot; i) {u G1.e[i].fr;v G1.e[i].to;w G1.e[i].w;if(G1.d[v] G2.d[u] w DIS) puts(HAPPY);else if(G3.bi[i]) puts(SAD);else puts(SOSO);} return 0 ;
}
