bestcoder round #1

1、拓扑排序。要求输出小的数尽量靠前，而不是字典序

可採用逆序拓扑方法。

(好多方法倒着来就是一片新天地...

自己曾经做过的题肿么能够又跪！

2、分块方法

详细便是每次更新x结点，仅仅更新与x结点相邻的点而且点的度数比x大的。

比x结点度数大的点不超过 sqrt(2m)

(事实上想想还是蛮显然的比方结点x要有m度,若与x相邻的点的度数都比x大，度数为m+1度，则为m+1度的这些点会有m+1条边。((m+1)*m-m)即为结果

附个代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define clr(x) memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back

#define INF 0x3c3c3c3c
typedef long long LL;

const int maxn = 1e5+200;
int deg[maxn];
vector<int> G[maxn];
int w[maxn], sum[maxn], num[maxn];
typedef struct edge{
    int x, y;
}edge;

int main()
{
   // fp1;
    edge Edge[maxn];
    int T, n, m, u, v;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d", &n, &m);
        clr(deg); clr(w); clr(sum);
        for(int i = 0;i < maxn;i++) G[i].clear();
        for(int i = 1;i <= m;i++){
            scanf("%d %d", &Edge[i].x, &Edge[i].y);
            deg[Edge[i].x]++;  deg[Edge[i].y]++;
        }
        for(int i = 1;i <= m;i++){
            if(deg[Edge[i].x] < deg[Edge[i].y]) {
                G[Edge[i].x].pb(Edge[i].y);
            }
            else G[Edge[i].y].pb(Edge[i].x);
        }
        int q, op;
        scanf("%d", &q);
        while(q--){
            scanf("%d", &op);
            if(op == 0){
                scanf("%d %d", &u, &v);
                w[u] += v;
                for(int i = 0;i < G[u].size();i++){
                    sum[G[u][i]] += v;
                    //printf("~%d %d
", u, G[u][i]);
                }
            }
            else {
                scanf("%d", &u);
                int ans = sum[u];
                for(int i = 0;i < G[u].size();i++){
                    ans += w[G[u][i]];
                }
                printf("%d
", ans);
            }
        }

    }
    return 0;
}

3、网络流？

ps: 我感受到了来自自己内心深处的囧状....