129 条题解
-
6
PowderHan LV 10 @ 2017-05-04 08:13:10
Accepted
/in/foo.cc: In function 'void check()':
/in/foo.cc:127:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
if(!vis[i])
^状态 耗时 内存占用
#1 Accepted 2ms 2.59MiB
#2 Accepted 6ms 2.582MiB
#3 Accepted 2ms 2.59MiB
#4 Accepted 5ms 2.715MiB
#5 Accepted 22ms 2.602MiB
#6 Accepted 18ms 2.625MiB
#7 Accepted 23ms 2.723MiB好题啊
陷阱蛮多的Orz
提供了一些新的套路23333
第一眼看过去 觉得是个SPFA裸题啊
后面感觉不对 没这么简单
出题人黑良心
当输入的图不是连通图时,SPFA(s)能做的就只是找出源点s所在的连通分量中的负环而已。
也就是说如果图中存在环,但不在源点所在的连通分量内的话,就会输出一堆的NoPath,
而不是-1,从此WA没救。
解决方案:
添加一个数组vis,来确定某个点是否访问过
(因为如果不在源点的连通分量内的点在SPFA的过程中时不会访问到的)。
然后每一个没有访问过的点都来一遍SPFA,以此来检查是否存在负环。
每次SPFA完了之后再将每个在这一次SPFA中 访问过的点的vis设为true,判断的标准:
是否进入过队列。
小优化:
dist[source]< 0 那么就存在负环,因为dist[source]本来为0,
结果跑了一圈成负的了,那说明有负环。
首先我们看到我们要先处理有没有负权环的问题
这个明显要独立做出来
就是我们先定一个vis数组标记点是否访问过
然后每次对于一个未访问的点
SPFA一下 并在SPFA中把到过的点标记访问过
那么我们可以知道 如果和这个点连通】
那么一定就是能走到(能标记到访问)
所以我们下一次就直接从没有访问过的点继续SPFA
即我们一次SPFA可以处理掉一个SCC中是否有负权环的问题
然后一直SPFA完所有的强连通分量
然后处理完后确定没有环了
我们就可以进行正常的SPFA求出最短路了
Orz因为怕麻烦啊
SPFA两种(一种要用到vis一种不要用到vis)就合在一起了
所以检查完负权环后
就要将vis数组清为0防止被SPFA中的判断vis误伤啊
然后就可以直接暴力做了
裸的SPFA好激动啊
注意一下这里SPFA中的小优化
上面也说了
嗯挺好用的Orz
好题
处理负权边和不连通问题
QAQ
随便读入优化一下飞快#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <stack> using namespace std; char rd; int pn; template<typename Type> inline void read(Type& v) { pn=1; while((rd=getchar())<'0'||rd>'9') if(rd=='-') pn=-1; v=rd-'0'; while((rd=getchar())>='0'&&rd<='9') v=v*10+rd-'0'; v*=pn; } template<typename Type> inline void out(Type v,bool c=1) { if(v==0) putchar(48); else { if(v<0) { putchar('-'); v=-v; } int len=0,dg[20]; while(v>0) { dg[++len]=v%10; v/=10; } for(int i=len;i>=1;i--) putchar(dg[i]+48); } if(c) putchar('\n'); else putchar(' '); } const int MAXN=1005; const int MAXM=200005; const int INF=0x7fffffff; struct Edge { int to,w,nxt; Edge() { to=nxt=-1; w=0; } }e[MAXM]; int fisrt[MAXN]; int tot; int n,m,s; inline void Add_Edge(int u,int v,int w) { e[++tot].to=v; e[tot].w=w; e[tot].nxt=fisrt[u]; fisrt[u]=tot; } void init() { memset(fisrt,-1,sizeof(fisrt)); read(n); read(m); read(s); int u,v,w; for(int i=1;i<=m;i++) { read(u); read(v); read(w); Add_Edge(u,v,w); } } bool vis[MAXN],inq[MAXN]; int cnt[MAXN]; int dis[MAXN]; queue<int> q; bool spfa(int s) { for(int i=1;i<=n;i++) dis[i]=INF; memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); while(!q.empty()) q.pop(); dis[s]=0; q.push(s); inq[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; if(dis[s]<0) return 0; for(int i=fisrt[u];i!=-1;i=e[i].nxt) { int& v=e[i].to; int& w=e[i].w; if(vis[v]) continue; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!inq[v]) { q.push(v); inq[v]=1; } if(++cnt[v]>n) return 0; } } } for(int i=1;i<=n;i++) vis[i]=vis[i]||cnt[i]; return 1; } void check() { for(int i=1;i<=n;i++) if(!vis[i]) if(!spfa(i)) { cout<<-1<<endl; exit(0); } else continue; } void work() { memset(vis,0,sizeof(vis)); spfa(s); for(int i=1;i<=n;i++) if(dis[i]==INF) cout<<"NoPath"<<endl; else out(dis[i]); } int main() { init(); check(); work(); return 0; }
**code by PowderHan**
-
42017-10-16 18:50:39@
额,图连不连通怎么判?加一个超级源,将它与每个点连一条权值为0的边,跑一边spfa即可
// vijos P1053#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define ins(u,v,w){e[++cnt]=(edge){v,h[u],w};h[u]=cnt;} using namespace std; const int N=1e3+5,M=1e5+5,inf=1e9+5; inline int read(){ int x=0,f=1,c=getchar(); for(;c< '0'||c >'9';c=getchar())if(c=='-')f=-1; for(;c>='0'&&c<='9';c=getchar())x=x*10+c-48; return x*f; } int n,m,s,u,v,w; struct edge{int to,nxt,w;}e[M+N]; int h[N],cnt; inline void lop(int &x){if(++x==N) x=1;} int q[N],head,tail,d[N],nc[N];bool inq[N]; bool spfa(int s){ head=tail=0; for(int i=1;i<=n;++i) d[i]=inf,inq[i]=nc[i]=0; q[tail]=s;inq[s]=nc[s]=1;lop(tail);d[s]=0; while(head!=tail){ int u=q[head];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].nxt) if(d[e[i].to]>d[u]+e[i].w){ d[e[i].to]=d[u]+e[i].w; if(!inq[e[i].to]){ inq[e[i].to]=1;q[tail]=e[i].to;lop(tail); if(++nc[e[i].to]>n) return false; } } } return true; } int main(){ n=read();m=read();s=read(); for(int i=1;i<=m;++i){ u=read();v=read();w=read(); if(u==v&&w<0) {puts("-1");return 0;} if(u!=v) ins(u,v,w); } int ss=n+1; for(int i=1;i<=n;++i) ins(ss,i,0); if(!spfa(ss)) {puts("-1");return 0;} spfa(s); for(int i=1;i<=n;++i){ if(d[i]>=inf) puts("NoPath"); else printf("%d\n",d[i]); } return 0; }
-
22016-06-09 12:20:10@
裸奔弗洛伊德
```c++
记录信息
评测状态 Time Limit Exceeded
题目 P1053 Easy sssp
递交时间 2016-06-09 12:14:34
代码语言 C++
评测机 ShadowShore
消耗时间 6481 ms
消耗内存 5408 KiB
评测时间 2016-06-09 12:14:41
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 5404 KiB, score = 0
测试数据 #1: TimeLimitExceeded, time = 1015 ms, mem = 5392 KiB, score = 0
测试数据 #2: TimeLimitExceeded, time = 1140 ms, mem = 5408 KiB, score = 0
测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 5396 KiB, score = 0
测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 5392 KiB, score = 0
测试数据 #5: Accepted, time = 1265 ms, mem = 5408 KiB, score = 25
测试数据 #6: TimeLimitExceeded, time = 1031 ms, mem = 5396 KiB, score = 0
TimeLimitExceeded, time = 6481 ms, mem = 5408 KiB, score = 25
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0xfffff,maxn = 1001;
long n,m,start,v[maxn][maxn];
bool s[maxn][maxn];
void input()
{
memset(s,false,sizeof(s));
scanf("%ld %ld %ld",&n,&m,&start);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
v[i][j] = INF;
for (int i = 1,a,b,c;i <= m;i++)
{
scanf("%d %d %d",&a,&b,&c);
v[a][b] = c;
s[a][b] = true;
}
}
#include <algorithm>
void floyd()
{
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
v[i][j] = min(v[i][j],v[i][k] + v[k][j]);
}
void work()
{
floyd();
for (int i = 1;i <= n;i++)
v[i][i] = 0;
for (int k = 1;k <= n;k++)
for (int i = 1;i <= k-1;i++)
for (int j = i+1;j <= k-1;j++)
if (s[i][j] && s[j][k] && v[k][i])
if(v[i][j]+v[j][k]+v[k][i] < 0)
{
printf("-1");
exit(0);
}
}
void output()
{
for (int i = 1;i <= n;i++)
if (v[start][i] == INF)
printf("NoPath");
else
printf("%ld\n",v[start][i]);
}
int main()
{
input();
work();
output();
return 0;
}
``` -
12016-01-30 21:48:30@
本题看起来比较简单,题目也比较清楚,但是隐藏了很多陷阱,首先此题要求找负环,如果有输出-1,如果没有输出S到所有边的距离。
建图很简单,数据范围__N<=1000__,直接用矩阵存入。
但是此题的边__有重复__!,建边的时候要注意选最小的。(用邻接表存有点麻烦)
点若入队>=n次或__dist[出发点]<0__则有负环,对每个点SPFA求负环绝对超时。
所以用__Swim数组__储存经过的点,下次求负环时直接跳过标记的点。
###code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x7f7f7f
#define MAX1 1010
#define MAX2 100010int N,M,S;
struct sssp{
//pretreatment初始化
void prepare(){
for(int i=1;i<=N;i++){
dist[i]=INF,swim[i]=false;
for(int j=1;j<=N;j++)
g[i][j]=INF;
}
}
//set map
int g[MAX1][MAX1];
inline void add(int u,int v,int val){
if(g[u][v]>val)//注意此处!数据中有重边
g[u][v]=val;
}
//
void got(int n){//建图
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
}
//SPFA
bool swim[MAX1];//标记已经遍历的点
bool ins[MAX1];//入队标记
int vis[MAX1];//记录入队次数
int dist[MAX1];//
queue<int> q;
bool SPFA(int s){//SPFA
for(int i=1;i<=N;i++) dist[i]=INF,vis[i]=0,ins[i]=false;
while(!q.empty()) q.pop();q.push(s);
vis[s]++,ins[s]=true,dist[s]=0;
while(!q.empty()){
int t=q.front();q.pop();ins[t]=false;
if(dist[s]<0) return true;
for(int i=1;i<=N;i++){
if(swim[i]==true) continue;
int u=g[t][i];
if(u!=INF&&dist[i]>dist[t]+u){
dist[i]=dist[t]+u;
if(!ins[i]){
q.push(i);ins[i]=true,vis[i]++;
if(vis[i]>=N/2) return true;
}
}
}
}
for(int i=1;i<=N;i++) swim[i]=swim[i]||vis[i];
return false;
}bool work(){
//for(int i=1;i<=N;i=i+(N/10)+1){ //随机化,减少遍历次数 i=i+(N/10)+1,但不用也可以过
for(int i=1;i<=N;i++){
if(!swim[i])
if(SPFA(i)) return true;
}
return false;
}
void work_out(){
if(work()){
printf("-1\n");
return;
}
else{
memset(swim,0,sizeof(swim));
SPFA(S);
for(int i=1;i<=N;i++){
if(dist[i]==INF) printf("NoPath\n");
else printf("%d\n",dist[i]);
}}
}
};
sssp car={0};int main(){
scanf("%d%d%d",&N,&M,&S);
car.prepare();
car.got(M);
car.work_out();return 0;
}
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 4276 KiB, score = 0
测试数据 #1: Accepted, time = 0 ms, mem = 4276 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 4276 KiB, score = 15
测试数据 #3: Accepted, time = 15 ms, mem = 4272 KiB, score = 15
测试数据 #4: Accepted, time = 46 ms, mem = 4276 KiB, score = 20
测试数据 #5: Accepted, time = 46 ms, mem = 4272 KiB, score = 25
测试数据 #6: Accepted, time = 62 ms, mem = 4272 KiB, score = 15
Accepted, time = 184 ms, mem = 4276 KiB, score = 100
我也是交了N次才AP!
鉴于没有一份详尽的题解,自己写了一份。 -
12009-10-14 18:20:43@
3行代码的程序
无语中...
begin
writeln(-1);
end.
编译通过...
├ 测试数据 01:答案错误...程序输出比正确答案长
├ 测试数据 02:答案错误...程序输出比正确答案长
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案错误... ├ 标准行输出
├ 错误行输出---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:75 有效耗时:0ms -
02021-02-19 23:18:12@
标答(大嘘)
#include <iostream> using namespace std; int main() { cout << -1 << endl; }
这。。。这题真的就搞人心态,我倒是想看看点2的数据到底长啥样,因为INF写了个114514191(只到1e8,当然是自己傻x了)第二个点只要去掉dist[t] < 0就能过,加上就过不了,后来换成INF = 1e9,再在邻接矩阵处加了一个判定if (f[u][v] != INF),两者应该任取其一就能过了。血的教训啊!
思路的话,基本就是优化Bellman-Ford,先判断有没有负权环,要注意可能会有不和源点连通的块,每个之前没跑过的点都访问一次就行了,上面 青衫白叙 的超级源点感觉更优雅方便一点,懒得改了。
判断负权环:
1. 考虑自环,在n个点的图中,任意一点最多只能和n个点有边,那理论上限就是我经过每个边都更新一次这个点,不能更多了(吗?其实很好奇会不会有更复杂,更准确地描述),所以当一个点更新数超过n(inq_cnt[u] > n)时,直接干掉。
2. 任意一次做Bellman-Ford时一旦出现源点dist[s] < 0,那也直接干掉。为什么?从源点出发,dist[s] < 0就是从一条路出去再回到源点,距离为负,那再重复一次同样的路线很明显会继续减小,必然是环,直接干掉。Debug:
1. 如之前所述,INF不能定太小或者不判定,我只能猜要不是爆精度了,要不是别的边权绝对值都很大,导致某条INF的边加那点的dist[u]还比原来的dist[v]要小;但是问题在于既然能有这样的路径被判定成负权环,为什么(inq_cnt[] > m)的判定就不会受影响呢?理论上来说,只要有被判定成负权环,迟早也会被这种方法判断到。但是仅有这个判断的时候却过了点二,非常搞笑。
2. 前面省时间加了prev_vis[]数组,可以不用额外访问单向边指向的访问过的部分,在判定完没负权环以后还要注意memset(0)再Bellman-Ford,不然算法碰到之前标记访问过的源点直接罢工了,原地爆炸。细节挺多,抓耳挠腮。。。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int MAXN = 1e3 + 145, INF = 1e9; int n, m, s; int f[MAXN][MAXN], dist[MAXN], inq_cnt[MAXN]; bool vis[MAXN], prev_vis[MAXN], inq[MAXN]; //Visited in this cycle; Visited in prev cycles; Nodes in queue. queue<int> q; int read() { int f = 1, x = 0; char ch = getchar(); if (ch == '-') { f = -1; ch = getchar(); } while ('0' <= ch && ch <= '9') { x *= 10; x += ch - '0'; ch = getchar(); } return f * x; } int bellmanford(int t) { for (int i = 0; i <= n; i++) { dist[i] = INF; vis[i] = false; } while (!q.empty()) q.pop(); q.push(t); dist[t] = 0; while (!q.empty()) { int u = q.front(); q.pop(); if (inq_cnt[u] > n || dist[t] < 0) return -1; vis[u] = true; inq[u] = false; for (int v = 1; v <= n; v++) { if (prev_vis[v] || f[u][v] == INF) continue; if (dist[u] + f[u][v] < dist[v]) { dist[v] = dist[u] + f[u][v]; if (!inq[v]) { q.push(v); inq_cnt[v]++; inq[v] = true; } } } } for (int i = 1; i <= n; i++) prev_vis[i] |= vis[i]; return 0; } int main() { n = read(); m = read(); s = read(); for (int u = 1; u <= n; u++) { for (int v = 1; v <= n; v++) { f[u][v] = INF; } } for (int i = 1; i <= m; i++) { int u, v, w; u = read(); v = read(); w = read(); f[u][v] = min(f[u][v], w); } int status_code = 0; for (int i = 1; i <= n; i++) { if (!prev_vis[i]) { status_code = bellmanford(i); if (status_code == -1) { cout << -1 << endl; return 0; } } } memset(prev_vis, 0, sizeof(prev_vis)); memset(inq_cnt, 0, sizeof(inq_cnt)); bellmanford(s); for (int i = 1; i <= n; i++) { if (dist[i] == INF) { cout << "NoPath" << endl; } else { cout << dist[i] << endl; } } return 0; }
-
02012-10-26 21:54:27@
├ 测试数据 01:答案正确... (0ms, 12492KB)
├ 测试数据 02:答案正确... (0ms, 12492KB)
├ 测试数据 03:答案正确... (0ms, 12492KB)
├ 测试数据 04:答案正确... (0ms, 12492KB)
├ 测试数据 05:答案正确... (0ms, 12492KB)
├ 测试数据 06:答案正确... (0ms, 12492KB)
├ 测试数据 07:答案正确... (0ms, 12492KB)终于ac了。。。这套题各种第七个点wa。。。我也不知道为什么,把整道题重新写了一遍居然就ac了,真是神奇。
这道题判断负环我用的是dist,如果有负环那么这个负环一定和start相连。 -
02012-07-18 15:00:46@
囧编译通过... ├ 测试数据 01:答案正确... 0ms ├ 测试数据 02:答案正确... 0ms ├ 测试数据 03:答案错误...程序输出比正确答案长 ├ 测试数据 04:答案正确... 0ms ├ 测试数据 05:答案正确... 0ms ├ 测试数据 06:答案错误...程序输出比正确答案长 ├ 测试数据 07:答案错误... ├ 标准行输出 ├ 错误行输出 ------------------------- Unaccepted 有效得分:45 有效耗时:0ms
-
02010-03-14 15:55:56@
提交了26遍
甚至照标程改了n遍
但始终没A
最后的教训是
c++一定要用scanf和printf
不能用cin和cout!!!
-
02010-03-09 18:40:57@
郁闷啊。。。第七个数据怎么回事会比正解小...我连两点多路都处理了啊。。。
-
02009-11-09 14:29:17@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 25ms
├ 测试数据 07:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:25ms
A了!虽然不是巨快如闪电
就是先对s用spfa,如果没有出现负权环就对与s不连通的点spfa
纠结啊,还是过了。。 -
02009-11-09 13:32:03@
感觉dfs n*n 不能判断负环啊。
应该是cheat吧。
对每个连同块。spfa才是王道 -
02009-11-04 08:09:46@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms判断环有个很好的优化
while(op < cl)
{
k = q[op];
v[k] = true;
for(j = e[k] ; j != -1 ; j = edge[j].next)
{
i = edge[j].t;
if(d[k] + edge[j].v < d[i])
{
d[i] = d[k] + edge[j].v;
if(!inq[i])
{
inq[i] = true;
q[cl] = i;
cl++;
co[i]++;
if(co[i] >= n - 1)return -1;
}
}
}
inq[k] = false;
op++;
if(d < 0) //在这里是一个环的优化
{
return -1;
}
} -
02009-11-02 23:20:16@
经过无数次提交wa的惨痛教训,第2组显示标准输出比选手输出长的同学注意判断负环的时候要写>n 不能写 >=n 啊!!!
-
02009-11-02 22:35:01@
lx正解,,此题最ws的地方就是和s不连的负环。。哎,,阴险啊。。是说这通过率....
-
02009-10-29 22:09:01@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms数据弱,每个联通块只要SPFA一下找负权环就行了。没出那种用每个联通块的第一个点做SPFA会出错的数据。比如
4 4 1
1 2 5
2 3 -1
3 4 -1
4 2 -1
我们用1做SPFA,显然没办法找到负权环2 3 4。
所以深搜找负权环比较好。但是我太菜了,以至于老超时,于是用上述方法cheat了。实在囧啊! -
02009-10-24 10:14:34@
35次提交后得到的教训。。。要用int64,初值要大一些
-
02009-10-06 21:17:02@
为啥你们能秒杀。。
-
02009-10-06 19:58:41@
1.居然有不和S在一个连通块里面的负环。。。。。
2.不看题解不知道。。。读进来的可能有重边。。要取最小的那个。。orz后来者注意。。
-
02009-10-03 09:10:28@
这个题好猥琐~~~