• 注册
当前位置：1313e > 默认分类 >正文

预习计划

会的东西好少好少.....还好多好多都不记得...0.0

每天瞅(预)下(习)以前做的题目叭><

10.10

网络流

最大流

cf 628 f Bear and Fair Set

 有 n 个数，mod 5 == 0 = mod %5 == 1 = mod % 5 == 2 = mod % 5 == 3 = mod % 4

每个数的大小不超过 b

然后 有 q 个限制，在 [1,r] 的范围内选择了  x 个数

问可不可能

因为 一个数 mod 5 只有 1 种可能，所以 源点向 每个余数 连边，容量 为 n/5

每个余数向 每个区间连边，容量 为 这个区间 为这个余数的个数

每个区间向汇点连边，容量 为这个区间的大小，看是否满流

 10.11

cf 653 d Delivery Bears

n 个点，m 条边，每条边有一个容量 ci ，有  x 只熊，每只熊 背的货物的重量相同，问最多能够运多少货物

二分 每只熊 能够背的货物，然后每条边的容量就是有几只熊，再check 下 是否满流

 

拆点

poj 3281 Dining

有 f 种食物，d 种饮料，每种食物，饮料只能分给一头牛，问最后有多少头牛能够吃到自己喜欢的食物和饮料

加 一个 源点，源点连向食物，将牛拆点成 i ,i' 食物连 i , i 和 i' 连边，容量为点的容量，i' 向饮料连边，饮料再向汇点连边

http://blog.csdn.net/accelerator_/article/details/41076999

点有容量：可以进行拆点，一个点拆成i和i'，i作为入点，i'作为出点，然后i和i'之间连一条边，容量就是点的容量，然后流入i点的连向入点，流出的，从出点连出去

拆边

没做过...

 

10.13

最小割

hdu 5294 Tricks Device

第一个求的是最短路还能够存在，最多可以破坏掉多少条边

第二个求的是至少破坏掉多少条边最短路就不存在了

第一个是在求最短路的时候，记录下 到 v 点的最少边数

第二个是把在最短路上的边容量为 1 ，跑最大流

 

---------------昏割线-----------------------------------------------------------------

二分图最大匹配

 

二分图最佳完美匹配

LA4043 白薯例题

给出 n 个白点，n 个黑点，需要用 n 条不相交的线段把它们连接起来

白点，黑点连边，边权 为 两点之间的欧几里得距离

还做过一种，求最小的，边权取负的就好...

 

 -------------------昏割线------------------------------------------------

连通性

dfs 判连通

并查集判连通

判断一个连通分量是不是二分图

割点：删掉这个点使得图不连通的点

桥：删掉这条边使得图不连通的边...注意重边

边双连通分量：任意两点之间至少存在两条边不重复的路径

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 using namespace std;
  9 typedef long long LL;
 10 const int maxn = 4e5+5;
 11 
 12 int n,m,vis[maxn];
 13 LL dp[maxn],w[maxn],iw[maxn];
 14 vector<int> g[maxn],bcc[maxn],e[maxn];
 15 int bcc_cnt,dfs_clock,bccno[maxn],dfn[maxn],top,low[maxn],iscut[maxn],pre[maxn],S[maxn];
 16 
 17 int sz,root;
 18 mapint,int>,int> id;
 19 int ans[maxn][2];
 20 
 21 void init(){
 22     bcc_cnt = n;
 23     dfs_clock = top = 0;
 24     memset(bccno,0,sizeof(bccno));
 25     memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
 26     memset(iscut,0,sizeof(iscut));
 27     memset(dp,0LL,sizeof(dp));
 28     memset(vis,0,sizeof(vis));
 29 }
 30 
 31 
 32 void tarjan(int u, int fa)
 33 {
 34     dfn[u] = low[u] = ++dfs_clock;
 35     S[top ++] = u;
 36     bool flag = false;
 37     for(int i = 0; i < g[u].size(); i++)
 38     {
 39         int v = g[u][i];
 40         if(v == fa && !flag) {flag = true; continue;}
 41         if(!dfn[v])
 42         {
 43             tarjan(v, u);
 44             low[u] = min(low[u], low[v]);
 45         }
 46         else if(!bccno[v]) low[u] = min(low[u], dfn[v]);
 47     }
 48 
 49     if(low[u] == dfn[u])
 50     {
 51         bcc_cnt++;
 52         int cnt = 0;
 53         while(1)
 54         {
 55             int x = S[--top];
 56             bccno[x] = bcc_cnt;
 57             cnt++;
 58             if(x == u) {
 59                 if(cnt > sz){
 60                     sz = cnt;
 61                     root = u;
 62                 }
 63                 break;
 64             }
 65         }
 66     }
 67 }
 68 
 69 void dfs(int u,int fa){
 70     low[u] = 0;
 71     for(int i = 0;i < g[u].size();i++){
 72         int v = g[u][i];
 73         int now = id[make_pair(u,v)];
 74         if(!vis[now]){
 75             vis[now] = 1;
 76             ans[now][0] = v;
 77             ans[now][1] = u;
 78         }
 79         if(low[v]) dfs(v,u);
 80     }
 81 }
 82 
 83 void solve(){
 84     init();
 85     sz = 0;
 86     for(int i = 1;i <= n;i++){
 87         if(!dfn[i]) tarjan(i,-1);
 88     }
 89     dfs(root,0);
 90     printf("%d\n",sz);
 91     for(int i = 1;i <= m;i++){
 92         printf("%d %d\n",ans[i][0],ans[i][1]);
 93     }
 94 }
 95 
 96 int main(){
 97     int T;
 98     scanf("%d %d",&n,&m);
 99     for(int i = 1;i <= n;i++) g[i].clear();
100     int u,v;
101     id.clear();
102     for(int i = 1;i <= m;i++){
103         scanf("%d %d",&u,&v);
104         g[u].push_back(v);
105         g[v].push_back(u);
106         id[make_pair(u,v)] = i;
107         id[make_pair(v,u)] = i;
108     }
109 
110     memset(ans,0,sizeof(ans));
111     solve();
112 
113     return 0;
114 }
View Code

 

点双连通分量：任意两点之间至少存在两条点不重复的路径

 

 

 

 

 

 

 

 

数学

gcd

hdu 5930 GCD

给出 一列数，q 次操作，将 pos 处的数修改成 v ，询问所有区间的gcd 的种数

 

转载于:https://www.cnblogs.com/wuyuewoniu/p/5947580.html

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 162202241@qq.com 举报，一经查实，本站将立刻删除。

最新评论

欢迎您发表评论:

请登录之后再进行评论

登录
相关推荐
Copyright © 2023 - 2024 1313e All Rights Reserved