P2149 [SDOI2009]Elaxia的路线

提交 6.45k

通过 1.87k

时间限制 1.00s

内存限制 125.00MB

题目提供者 xmyzwls

难度省选/NOI-

历史分数100

提交记录

查看题解

题目描述

最近，Elaxia 和 w** 的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。

Elaxia 和 w** 每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。

现在已知的是 Elaxia 和 w** 所在的宿舍和实验室的编号以及学校的地图：
地图上有

输入格式

第一行两个正整数

第二行四个正整数 $x1,y1,x2,y2x_1,y_1,x_2,y_2x1,y1,x2,y2，分别表示 Elaxia 的宿舍和实验室及 w** 的宿舍和实验室的标号。$

接下来

输出格式

一行一个整数表示答案。（即最长公共路径的长度）

输入输出样例

输入 #1

输出 #1

思路

　　这道题一开始拿到的思路是给最短路全打上标记，但是发现一个坑，这里交了只有10分，就是标记的方向问题。

　　后来想了想可以把标记问题转换一下。

　　假设 x1 -> y1 上存在一点对 (u, v) ，且 uv 间有路，若 dis[x1][u] + dis[u][v] + dis[v][y1] == dis[x1][y1] 则说明 uv 一定是一组被标记的带方向的最短路上一个点对。

　　我们跑四次dijkstra处理出 x1->y1, x2->y2, y1->x1, y2->x2的dis，之后枚举所有的边，找到所有的形似uv这样被标记的点对，通过四次拓扑排序建立DAG图，在DAG图上找最长链即可。

　　因为要跑多次拓扑和dijkstra，初始化是很重要的。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 2e5 + 7;
 47 const int inf  = 0x3f3f3f3f;
 48 
 49 int head[maxn << 2], edge[maxn << 2], w[maxn << 2], nxt[maxn << 2];
 50 int cnt;
 51 
 52 inline void BuildGraph (int u, int v, int c) {
 53     cnt++;
 54     edge[cnt] = v;
 55     nxt[cnt]  = head[u];
 56     w[cnt] = c;
 57     head[u] = cnt;
 58 }
 59 
 60 struct node {
 61     int u,v;
 62     bool operator <(const node &t) const {
 63         return u > t.u;
 64     }
 65 };
 66 
 67 struct Node {
 68     int v, w;
 69 };
 70 
 71 int n,m,s,t;
 72 int dis[10][maxn];
 73 bool vis[maxn];
 74 int minn = 0;
 75 
 76 vector <Node> e[maxn];
 77 queue<Node> que;
 78 
 79 priority_queue < node > q;
 80 
 81 void dijkstra(int s, int id) {
 82     memset(vis, 0, sizeof(vis));
 83     for(int i = 1; i <= n; i++) {
 84         dis[id][i] = 0x3f3f3f3f;
 85     }
 86     dis[id][s] = 0;
 87     q.push({0,s});
 88     while(!q.empty()) {
 89         node temp = q.top();
 90         q.pop();
 91         if(vis[temp.v]) continue;
 92         vis[temp.v] = true;
 93         for(int i = head[temp.v]; i; i = nxt[i]) {
 94             int v = edge[i];
 95             int c = w[i];
 96             if(dis[id][v] > dis[id][temp.v] + c) {
 97                 dis[id][v] = dis[id][temp.v] + c;
 98                 q.push({dis[id][v],v});
 99             }
100         }
101     }
102 }
103 
104 int in[maxn];
105 int ddis[maxn];
106 int ans;
107 
108 void topo(int s1, int s2, int s3, int s4, int x1, int y1, int x2, int y2) {
109     for ( int i = 1; i <= n; ++i ) {
110         e[i].clear();
111     }
112     memset(in, -1, sizeof(in));
113     for ( int i = 1; i <= n; ++i ) {
114         for (int j = head[i]; j; j = nxt[j]) {
115             int u = i;
116             int v = edge[j];
117             int c = w[j];
118             //printf("dis[%d][%d]:%d c:%d dis[%d][%d]:%d dis[%d][%d]:%d\n",s1,u,dis[s1][u],c,s2,v,dis[s2][v],s1,y1,dis[s1][y1]);
119             if(dis[s1][u] + c + dis[s2][v] == dis[s1][y1]) {
120                 if(dis[s3][u] + c + dis[s4][v] == dis[s3][y2]) {
121                     if(in[u] == -1)
122                         in[u]=0;
123                     if(in[v] == -1)
124                         in[v]=0;
125                     in[v]++;
126                     e[u].push_back({v,c});
127                 }
128             }
129         }
130     }
131     while(!que.empty()) {
132         que.pop();
133     }
134     for ( int i = 1; i <= n; ++i ) {
135         if(in[i] == 0) {
136             Node temp;
137             temp.v = i, temp.w = 0;
138             que.push(temp);
139         }
140     }
141     memset(ddis, 0, sizeof(ddis));
142     while(!que.empty()) {
143         Node temp;
144         temp = que.front();
145         que.pop();
146         int u = temp.v;
147         for ( int i = 0; i < e[u].size(); ++i ) {
148             int v = e[u][i].v;
149             int c = e[u][i].w;
150             if(in[v] == -1) continue;
151             ddis[v] = max(ddis[v], ddis[u] + c);
152             //printf("ddis[%d]:%d\n",v, ddis[v]);
153             ans = max(ans, ddis[v]);
154             in[v]--;
155             if(in[v] == 0) {
156                 que.push(e[u][i]);
157             }
158         }
159     }
160 }
161 
162 int main()
163 {
164     scanf("%d %d",&n, &m);
165     int x1, y1, x2, y2;
166     scanf("%d %d %d %d",&x1, &y1, &x2, &y2);
167     
168     int a, b, c;
169     for (int i = 1; i <= m; ++i) {
170         scanf("%d %d %d",&a, &b, &c);
171         BuildGraph(a, b, c);
172         BuildGraph(b, a, c);
173     }
174     dijkstra(x1, 1);
175     dijkstra(y1, 2);
176     dijkstra(x2, 3);
177     dijkstra(y2, 4);
178     ans = 0;
179     topo(1,2,3,4,x1,y1,x2,y2);
180     topo(1,2,4,3,x1,y1,y2,x2);
181     topo(2,1,3,4,y1,x1,x2,y2);
182     topo(2,1,4,3,y1,x1,y2,x2);
183     cout << ans << endl;
184     return 0;
185 }