逃生
反向拓扑+优先队列+逆序输出
这里要注意，题中要求的不是输出字典序，而是要编号小的尽量考前（首先1尽量考前，然后2尽量考前。。）。
比如说 约束是 4->1,3->2，字典序答案就是3 2 4 1，但是编号小的尽量考前答案就是 4 1 3 2。
为什么正向建图不行呢？正向建图我们不知道怎么样才能最先找到编号为1的，然后再最先找到2的。。。拿上面这个例子来说，我们应该先找到4这样才能先使得1优先，但是这样的找法是没有规律的。
正解是反向建图，这样每次先找到编号大的，最后自然使得编号小的留在后。最后逆序输出即可。
注意一个样例
input: 1 3 1 3 1 answer: 3 1 2 而不是 2 3 1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define MAXN 30005
using namespace std;
vector<int> g[MAXN];
int in[MAXN];
int n;
void clear()
{
; i<=n; ++i)
{
g[i].clear();
;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int m;
scanf("%d%d",&n,&m);
clear();
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
g[b].push_back(a);
in[a]++;
}
priority_queue<int,vector<int>,less<int> > pq;
; i<=n; ++i)
)
pq.push(i);
vector<int> ans;
while(!pq.empty())
{
int p=pq.top();
pq.pop();
ans.push_back(p);
; i<g[p].size(); ++i)
{
int &u=g[p][i];
in[u]--;
if(!in[u]) pq.push(u);
}
}
; i>=; --i)
) printf("%d",ans[i]);
else printf(" %d",ans[i]);
printf("\n");
}
;
}
项目管理
维护一个sum[]和val[]的数组。sum中存比当前结点度大的点值的和，val存当前结点的值。对每个点开一个vector存比它度大的点集。
每次更新，更新自身的val，同时更新vector中点的sum。
每次查询，结果为自身sum与vector中点（除去与当前点度数相同的点，因为这部分结果已经在sum中了）的val的和。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define MAXN 100005
using namespace std;
vector<int> g[MAXN],big[MAXN];
int val[MAXN],sum[MAXN],in[MAXN];
void clear(int n)
{
; i<=n; ++i)
{
g[i].clear();
big[i].clear();
val[i]=sum[i]=;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
clear(n);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
in[a]++;
in[b]++;
}
; i<=n; ++i)
; j<g[i].size(); ++j)
if(in[g[i][j]]>=in[i])
big[i].push_back(g[i][j]);
int q;
scanf("%d",&q);
while(q--)
{
int cmd;
scanf("%d",&cmd);
)
{
int a,b;
scanf("%d%d",&a,&b);
val[a]+=b;
; i<big[a].size(); ++i)
sum[big[a][i]]+=b;
}
else
{
int a;
scanf("%d",&a);
int ans=sum[a];
; i<big[a].size(); ++i)
if(in[a]!=in[big[a][i]])
ans+=val[big[a][i]];
printf("%d\n",ans);
}
}
}
;
}