18 条题解
-
6
larryzhong LV 9 @ 2017-05-15 13:30:39
拓扑排序 （堆优化）：
#include <iostream> #include <vector> #include <queue> using namespace std; const int maxn = 100000; int _count[maxn], res[maxn]; vector<int> G[maxn]; priority_queue<int> que; int main() { int n, m; cin >> n >> m; while (m--) { int u, v; cin >> u >> v; u--; v--; _count[u]++; G[v].push_back(u); } for (int i = 0; i < n; i++) if (_count[i] == 0) que.push(i); int tmp = n; while (!que.empty()) { int u = que.top(); que.pop(); res[u] = tmp--; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; _count[v]--; if (_count[v] == 0) que.push(v); } } for (int i = 0; i < n; i++) cout << res[i] << " "; cout << endl; return 0; } -
3
caesar_199 LV 9 @ 2016-08-20 11:47:13
正向贪心没过样例，仔细想想发现正向贪心可能导致前面的点的编号很大，所以就用逆向贪心，每次找入度为零且编号尽量大的点，把它放在拓扑序列的列首，并且删除所有指向这个点的有向边。
代码实现如下，维护一个优先队列，只有当一个点的入度为零的时候才将它入队。
```c++
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;const int maxn = 100000 + 10;
const int maxm = 200000 + 10;int n, m;
int clock;
int cnt[maxn], id[maxn];
vector<int> G[maxn];
priority_queue<int> Q;int main () {
cin >> n >> m;while (m--) {
int u, v;
scanf("%d%d", &u, &v); u--; v--;
cnt[u]++;
G[v].push_back(u);
}for (int i = 0; i < n; i++) if (!cnt[i])
Q.push(i);clock = n;
while (!Q.empty()) {
int u = Q.top(); Q.pop();
id[u] = clock--;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
cnt[v]--;
if (cnt[v] == 0) Q.push(v);
}
}
for (int i = 0; i < n; i++) printf("%d ", id[i]);
return 0;
}
``` -
2
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;const int N = 100000 + 5;
int n, m, in[N], id[N];
vector<int> mp[N];
priority_queue<int> pq;int main() {
scanf("%d%d", &n, &m);
while (m--) {
int x, y; scanf("%d%d", &x, &y);
in[x]++;
mp[y].push_back(x);
}
int num = n;
for (int i = 1; i <= n; i++) if (!in[i]) pq.push(i);
while (!pq.empty()) {
int u = pq.top(); pq.pop();
id[u] = num--;
for (int i = 0; i < mp[u].size(); i++) {
int v = mp[u][i];
if (--in[v] == 0) pq.push(v);
}
}
for (int i = 1; i <= n; i++) printf("%d ", id[i]);
return 0;
} -
1
是我的理解有什么偏差么？题解里都说每次选入度为0的，我越想越不对，自己写了个每次选出度为0的，最开始后三个点TimeOut，最后用了优先队列才过的。
#include <iostream> #include <vector> #include <queue> using namespace std; int n,m; vector<int> edge[100001]; int a[100001]={0}; int ans[100001]; priority_queue<int> que; int main() { cin>>n>>m; int i,j; int index; int from,to; for(i=0;i<m;i++) { cin>>from>>to; edge[to].push_back(from); a[from]++; } int acc=n; for(i=1;i<=n;i++) { if(a[i]==0) { que.push(i); } } while(!que.empty()) { index=que.top(); que.pop(); ans[index]=acc; acc--; for(j=edge[index].size()-1;j>=0;j--) { i=edge[index][j]; a[i]--; if(a[i]==0) { que.push(i); } } } cout<<ans[1]; for(i=2;i<=n;i++) { cout<<' '<<ans[i]; } cout<<endl; return 0; } -
1
反向拓扑 + 堆优化
//
// main.cpp
// 1790
//
// Created by Jack Zhang on 2018/5/27.
// Copyright © 2018年 Jack Zhang. All rights reserved.
//#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
priority_queue<int/*, vector<int>, greater<int> */> stk;
const int maxn = 100010;
int n,m, in[maxn], a[maxn], newname;
vector <int> out[maxn];
int main(int argc, const char * argv[]) {
memset(in, 0, sizeof(in));
scanf("%d%d", &n, &m);
newname = n;
for(int i=0;i<m;i++) {
int x,y;
scanf("%d%d", &x, &y);
swap(x, y);
int flag = true;
for(int j=0;j<out[x].size();j++){
if(out[x][j] == y){
flag = false;
break;
}
}
if(flag){
out[x].push_back(y);
in[y]++;
}
}
for(int i=1;i<=n;i++){
if(in[i]==0) stk.push(i);
}
while(!stk.empty()){
int p = stk.top();
stk.pop();
a[p]=newname--;
for(int i=0;i<out[p].size();i++){
int to = out[p][i];
in[to]--;
if(in[to]==0) stk.push(to);
}
}
for(int i=1;i<=n;i++){
cout<<a[i];
if(i!=n)cout<<" ";
}
return 0;
} -
0
建反边，堆优化
type
ab=^node;
node=record
ed:longint;
nx:ab;
end;
var
i,n,m,l,z,x,y:longint;
ph:array[0..100000] of ab;
heap,a,d:array[0..100000] of longint;procedure swap(var x,y:longint);
var p:longint;
begin
p:=x;x:=y;y:=p;
end;procedure init(y,x:longint);
var i:ab;
begin
i:=ph[y];
new(ph[y]);
ph[y]^.ed:=x;
ph[y]^.nx:=i;
end;function get:longint;
var i,j:longint;
begin
get:=heap[1];
heap[1]:=heap[l];
dec(l);
i:=1;
while i shl 1<=l do
begin
j:=i shl 1;
if (j<l)and(heap[j]<heap[j+1]) then inc(j);
if heap[i]<heap[j] then
begin
swap(heap[i],heap[j]);
i:=j;
end
else
break;
end;
end;procedure put(x:longint);
var i,j:longint;
begin
inc(l);
heap[l]:=x;
i:=l;
while i>1 do
begin
j:=i shr 1;
if heap[j]<heap[i] then
begin
swap(heap[i],heap[j]);
i:=j;
end
else
break;
end;
end;procedure doit;
var i,j:longint;
p:ab;
begin
l:=0;
for i:=1 to n do
if d[i]=0 then
begin
put(i);
d[i]:=maxlongint;
end;
while l>0 do
begin
i:=get;
p:=ph[i];
inc(z);
a[i]:=z;
while p<>nil do
begin
j:=p^.ed;
dec(d[j]);
if d[j]=0 then
begin
put(j);
d[j]:=maxlongint;
end;
p:=p^.nx;
end;
end;
end;begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
inc(d[x]);
init(y,x);
end;
doit;
for i:=1 to n do
write(n-a[i]+1,' ');
end. -
0
2233702013 LV 8 @ 2016-08-28 10:54:56
我已经发现vijos的cin和cout很神奇了。就算关闭流同步依然慢成狗。换成scanf瞬间降一半。
思路楼下说过了，这里给出29行代码
c++
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int n,m,x,y,i,count;
scanf("%d%d",&n,&m);count=n;
vector<vector<int> >list(n+1);vector<int> in(n+1),a(n+1);priority_queue<int> que;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
list[y].push_back(x);in[x]++;
}
for(i=1;i<=n;i++)if(!in[i])que.push(i);
while(!que.empty())
{
int load=que.top();
que.pop();a[load]=count--;
for(vector<int>::iterator ite=list[load].begin();ite!=list[load].end();ite++)
if(!a[*ite])
{
in[*ite]--;
if(!in[*ite])que.push(*ite);
}
}
for(i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
-
0
我在我的博客里 写了这个算法的证明 感兴趣的朋友可以 参考一下 欢迎指出错误
http://www.cnblogs.com/vb4896/p/4083650.html -
0
逆拓扑排序+堆
逆拓扑排序，每次取出入度为零的节点时，要取出标号最大的节点。
找标号最大的节点可以用堆进行优化
代码如下：type
node=^rec1;
rec1=record data:longint;next:node; end;
rec2=record ru:longint;link:node; end;
var
i,n,m,l,z,x,y:longint;p:node;
g:array[0..100000] of rec2;
heap,a:array[0..100000] of longint;procedure swap(var x,y:longint);
var p:longint;
begin
p:=x;x:=y;y:=p;
end;procedure swim;
var i,j:longint;
begin
i:=1;
while i shl 1<=l do
begin
j:=i shl 1;
if (j<l)and(heap[j]<heap[j+1]) then inc(j);
if heap[i]<heap[j] then
begin
swap(heap[i],heap[j]);i:=j;
end
else break;
end;
end;procedure add(x:longint);
var i,j:longint;
begin
inc(l);heap[l]:=x;i:=l;
while i>1 do
begin
j:=i shr 1;
if heap[j]<heap[i] then
begin
swap(heap[i],heap[j]);i:=j;
end
else break;
end;
end;procedure toposort;
var i,j:longint;p:node;
begin
l:=0;
for i:=1 to n do
if g[i].ru=0 then
begin
add(i);g[i].ru:=maxlongint;
end;
while l>0 do
begin
i:=heap[1];heap[1]:=heap[l];
dec(l);swim;p:=g[i].link;
inc(z);a[i]:=z;
while p<>nil do
begin
j:=p^.data;dec(g[j].ru);
if g[j].ru=0 then
begin
add(j);g[j].ru:=maxlongint;
end;
p:=p^.next;
end;
end;
end;begin
readln(n,m);
for i:=1 to n do
begin
g[i].ru:=0;g[i].link:=nil;
end;
for i:=1 to m do
begin
readln(x,y);inc(g[x].ru);new(p);
p^.data:=x;p^.next:=g[y].link;g[y].link:=p;
end;
toposort;
for i:=1 to n do write(n-a[i]+1,' ');
end. -
0
这道题做了好长时间 一开始 证明了正向的贪心不对后 虽然也想到了 反向的贪心 但始终说服不了自己 于是写了一个 dfs计算每个点可以走到的最小点 以及达到这个最小点的 path 然后写了个三关键字的堆 好 然后标号 。。。。。这样是错的 以路径为一个关键字的贪心不太正确
然后 听了神牛的讲评
反向的严格证明 不知道
但是 正向贪心 显然会错误 但是 反向的话 出度为零 的最大点为最后一个丝毫不违反 规则 并且可以说 很好的迎合了“国王”的规则 所以 。。。就这样 （语言表达能力好差 ）-
lsdsjy @ 2014-10-15 16:38:38
居然有人跟我的想法一样= =
只比较最小点的确是错的 稍微说明（证明？）一下就是：两条路径所能走到的最小点可能是一样的，此时就要比较次小点，次小点一样的时候又要继续比较两条路径上第三小的点……
-
-
0
yanyao1314 LV 9 @ 2013-08-03 14:57:57
为什么要反过来？？？
-
0
过了七个点，最后三个点过不了，代码如下，不知道大家有没有好的方法，过掉最后三个大数据的点
program vijos1790;
type
tnode=^node;
node=record
p:longint;
next:tnode;
end;
var
tosort,tosort2,after:array[1..100010] of longint;
f:array[1..100010] of tnode;
i,j,n,m,u,v,k:longint;
t:tnode;
function find(u,v:longint):boolean;
var temp:tnode;
begin
temp:=f[u];
while temp<>nil do
begin
if temp^.p=v then
exit(true);
temp:=temp^.next;
end;
exit(false);
end;begin
readln(n,m);
fillchar(after,sizeof(after),0);for i:=1 to m do
begin
readln(u,v);
if ( not find(u,v)) then
begin
inc(after[u]);
new(t);
t^.p:=v;
t^.next:=f[u];
f[u]:=t;
end;end;
i:=n;
while i>0 do
begin
j:=n;
while after[j]<>0 do dec(j);
after[j]:=-1;
for k:=1 to n do
if find(k,j) then
begindec(after[k]);
end;tosort[i]:=j;
dec(i);
end;
for i:=1 to n do
tosort2[tosort[i]]:=i;
for i:=1 to n-1 do
write(tosort2[i],' ');
writeln(tosort2[n]);end.
-
优先队列
-
w_ypl @ 2013-10-29 18:51:25
堆优化
-
ydfq @ 2015-04-09 11:28:43
写堆
-
-
-2
缩缩缩
#include <iostream> #include <vector> #include <queue> using namespace std; const int MAXN = 100000 + 10; vector<int> g[MAXN]; priority_queue<int> q; int n, cnt[MAXN], u, v, m, tick, res[MAXN]; int main(){ cin.sync_with_stdio(false); cout.sync_with_stdio(false); cin >> n >> m; tick = n; for (int i = 1; i <= m; i++){ cin >> u >> v; g[v].push_back(u); cnt[u]++; } for (int i = 1; i <= n; i++) if (!cnt[i]) q.push(i); while (!q.empty()){ int cur = q.top(); q.pop(); res[cur] = tick--; for (int i = 0; i < g[cur].size(); i++) if (!--cnt[g[cur][i]]) q.push(g[cur][i]); } for (int i = 1; i <= n; i++) cout << res[i] << " "; cout << endl; return 0; }
larryzhong
LV 9
@ 2017-05-15 13:30:39
- 1
