COJ 3016 WZJ的图论问题

传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=1046

试题描述：

WZJ又有一个问题想问问大家。WZJ用数据生成器生成了一个虚拟旅游区。这个旅游区由N个城市构成，标号从1到N，这些城市之间由M条双向道路连接。
其中每个城市有一个游乐场，游客可以花costi的钱数去城市i的游乐场玩，并获得happyi的高兴值,但对于一个游乐场,游客只能去玩至多一次。
因为虚拟旅游区的内存有限，有时候WZJ被迫在系统中删去一些边，当然WZJ可能忘记一些已被删去的边。
另外有些同学想来体验，WZJ会给他money的钱数，并把他送到城市x，他能通过未删除的道路去一些城市的游乐场玩。
下面请你帮助WZJ完成Q次操作，操作分两种：
1、0 y：虚拟旅游区的内存有限，WZJ被迫在系统中删去边y（不保证边y未被删去，这时你可以忽略这次指令）。
2、1 x money：又来了一个同学想来体验，WZJ给了他money的钱数，并把他送到城市x，问在最多花money的钱数能得到的最大高兴值。

输入：

输入第一行为三个正整数N,M,Q。
接下来N行每行为两个正整数costi,happyi。
再接下来M行每行为两个正整数ui,vi。
最后Q行每行为一个操作。

输出：

对于每个操作2,输出结果单占一行。

输入示例：

3 4 10
1 2
2 7
1 4
1 2
2 3
1 3
1 1
1 1 2
1 1 1
0 1
1 1 1
1 1 2
0 2
1 1 2
0 2
0 3
1 1 3

输出示例：

7
4
4
7
6
2

其他说明：

1<=N<=10000, 1<=M,Q<=100000, 1<=ui,vi,x<=N, 1<=costi,money<=200, 1<=happyi<=100000，1<=y<=M

题解：时光倒流+背包dp

注意，加边的时候都搞成单向边了(,,• ₃ •,,)好神奇呀呀(｡•ˇ‸ˇ•｡)小健建就是NB呀呀呀(ㆀ˘･з･˘)

还有，结点要开2倍，我也不造为什么诺_( ﾟДﾟ)ﾉ

  1 #include <cstdio> 
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <queue>
  7 #define REP(s, n) for(int i = s; i <= n; i ++)
  8 #define RAP(s, n) for(int j = s; j <= n; j ++)
  9 #define DE(i) e[POS(i)].del
 10 #define POS(i) query[i].pos
 11 #define V(i) query[i].v
 12 #define ID(i) query[i].id
 13 #define ANS(i) query[i].ans
 14 #define COST(i) p[i].cost
 15 #define HA(i) p[i].happy
 16 using namespace std;
 17 const int maxn = 20000 + 1;
 18 const int maxm = 100000 + 1;
 19 const int maxma = 200 + 1;
 20 struct Point { int cost, happy; } p[maxn];
 21 struct Edge { 
 22     int u, v, del; 
 23     Edge() { del = 0; }
 24 }e[maxm];
 25 struct Tedge { int to, next; } adj[maxm];
 26 struct Questions {
 27     int pos, v, ans;
 28     bool id;
 29     Questions() { ans = 0; }
 30 }query[maxm];
 31 int Q, n, m, dp[maxn][maxma], f[maxn], tar_num[maxn], fch[maxn];
 32 int findset(int x){
 33     return x == f[x] ? x : f[x] = findset(f[x]);
 34 }
 35 int ms = 1;
 36 void AddEdge(int from, int to){
 37     adj[ms] = (Tedge) { to, fch[from] };
 38     fch[from] = ms ++;
 39     return ;
 40 }
 41 int que[maxn], tot;
 42 void dfs(int x){
 43     que[++ tot] = x;
 44     for(int i = fch[x]; i; i = adj[i].next) dfs(adj[i].to);
 45     return ;
 46 }
 47 void merge(int u, int v){
 48     int f1 = findset(u), f2 = findset(v);
 49     if(f1 == f2) return ;
 50     if(tar_num[f1] > tar_num[f2]) swap(f1, f2);
 51     tar_num[f2] += tar_num[f1]; tar_num[f1] = 0; f[f1] = f2;
 52     tot = 0; dfs(f1); AddEdge(f2, f1);
 53     REP(1, tot){
 54         int v = p[que[i]].cost, w = p[que[i]].happy;
 55         for(int j = 200; j >= v; j --) dp[f2][j] = max(dp[f2][j], dp[f2][j - v] + w);
 56     }
 57     return ;
 58 }
 59 void read(int &x){
 60     x = 0; int sig = 1; char ch = getchar();
 61     while(!isdigit(ch)) { if(ch == '-') sig = -1; ch = getchar(); }
 62     while(isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
 63     x *= sig; return ;
 64 }
 65 void init(){
 66     read(n), read(m), read(Q); int temp;
 67     REP(1, n) f[i] = i, tar_num[i] = 1;
 68     REP(1, n){
 69         read(COST(i)); read(HA(i));
 70         RAP(COST(i), 200) dp[i][j] = HA(i);
 71     }
 72     REP(1, m) read(e[i].u), read(e[i].v);
 73     REP(1, Q){
 74         read(temp); ID(i) = temp;
 75         if(!ID(i)) {
 76             read(POS(i));
 77             if(!DE(i)) DE(i) = i;
 78         }
 79         else read(POS(i)), read(V(i));
 80     }
 81     return ;
 82 }
 83 void work(){
 84     REP(1, m) if(!e[i].del) merge(e[i].u, e[i].v);
 85     for(int i = Q; i; i --){
 86         if(!ID(i) && DE(i) == i) merge(e[POS(i)].u, e[POS(i)].v);
 87         else ANS(i) = dp[findset(POS(i))][V(i)];
 88     }
 89     return ;
 90 }
 91 void print(){
 92     REP(1, Q) if(ID(i)) printf("%d
", ANS(i));
 93     return ;
 94 }
 95 int main(){
 96     init();
 97     work();
 98     print();
 99     return 0;
100 }