首页 > 代码库 > 最大流
最大流
我之前并没有听说过树上差分这么高级的东东，于是为了练手速花了40min敲了一个树剖套线段树，写好了线段树的一堆函数定义（maketree() pushdown() query() update()），剩着函数内部等待填充，感觉到一种绝望：还有那么多，要敲到啥时候啊。。。正在调整心态准备敲线段树时，突然想到，这题好像只是区间修改、单点查询？！哇，得救啦！[传送门](https://www.luogu.org/problem/show?pid=3368)
于是内心一片愉悦啊，愉快地敲完短得多的树状数组，顺利1A！
正经的题解：
增加一条x到y的路径，就是把x到y的所有点的点权加1，很容易想到这是树剖裸题的第一个操作（[传送门](https://www.luogu.org/problem/show?pid=3384)）,于是我很天真地套上了模板——树链剖分套线段树，但代码量对我这种手速不够的蒟蒻来说好长！于是急中生智换成了树状数组，代码少了整整90行（树剖裸题我的空行太多……）。上代码
1 #include<bits/stdc++.h> 2 #define lson(x) ((x)<<1) 3 #define rson(x) (((x)<<1)|1) 4 #define lowbit(x) (x)&(-(x)) 5 using namespace std; 6 7 int n,k; 8 9 struct Edge{ 10 int next,to; 11 }e[100010]; 12 int cnt=1,head[50010]; 13 void add_e(int u,int v) 14 { 15 e[cnt].to=v; 16 e[cnt].next=head[u]; 17 head[u]=cnt++; 18 } 19 20 struct tree{ 21 int fa; 22 vector<int> son; 23 int dep; 24 int num_to; 25 int wson; 26 int top; 27 int new_id; 28 }t[50010]; 29 bool vis[50010]; 30 int dfs1(int u,int fa,int depth) 31 { 32 vis[u]=1; 33 t[u].fa=fa; 34 t[u].dep=depth; 35 t[u].num_to=1; 36 for(int i=head[u],weightest=-1,w;i;i=e[i].next) 37 { 38 int v=e[i].to; 39 if(vis[v]) continue; 40 t[u].son.push_back(v); 41 w=dfs1(v,u,depth+1); 42 if(w>weightest) 43 { 44 t[u].wson=v; 45 weightest=w; 46 } 47 t[u].num_to+=w; 48 } 49 return t[u].num_to; 50 } 51 int num_id=1; 52 void dfs2(int u,int top) 53 { 54 t[u].top=top; 55 t[u].new_id=num_id++; 56 int sz=t[u].son.size(); 57 if(sz==0) 58 return; 59 dfs2(t[u].wson,top); 60 for(int i=0;i<sz;i++) 61 { 62 int v=t[u].son[i]; 63 if(v==t[u].wson) continue; 64 dfs2(v,v); 65 } 66 } 67 68 int s[50010]={0}; 69 void add(int node,int w) 70 { 71 while(node<n) 72 { 73 s[node]+=w; 74 node+=lowbit(node); 75 } 76 } 77 int ask(int node) 78 { 79 int ans=0; 80 while(node) 81 { 82 ans+=s[node]; 83 node-=lowbit(node); 84 } 85 return ans; 86 } 87 88 void up(int x,int y)////////////////////////////////////// 89 { 90 while(t[x].top!=t[y].top)//x向y上靠 即y.top 更高 91 { 92 if(t[t[x].top].dep<t[t[y].top].dep) swap(x,y); 93 add(t[x].new_id-1,-1); 94 add(t[t[x].top].new_id,1); 95 x=t[t[x].top].fa; 96 } 97 if(t[x].new_id>t[y].new_id) swap(x,y); 98 add(t[x].new_id,1); 99 add(t[y].new_id+1,-1);100 }101 int main()102 {103 scanf("%d%d",&n,&k);104 for(int i=1,x,y;i<n;i++)105 {106 scanf("%d%d",&x,&y);107 add_e(x,y);108 add_e(y,x);109 }110 dfs1(1,1,1);111 dfs2(1,1);112 113 for(int i=0,x,y;i<k;i++)114 {115 scanf("%d%d",&x,&y);116 up(x,y);117 }118 int maxn=s[1];119 for(int i=2;i<=50001;i++)120 {121 maxn=max(maxn,ask(i));122 }123 printf("%d",maxn);124 return 0;125 }
最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。