企业网站开发制作,做百度网络营销推广,做网站的公司 杭州,做外贸的国际网站有哪些内容刘汝佳的紫书差不多就告一段落吧#xff0c;我觉得可以了#xff0c;怎么说呢#xff0c;这书也陪着自己走了一年多了吧#xff0c;也目睹了从一个啥也不会的萌新到一个稍微会一点的萌新的转变。 差不多开始下本书吧#xff0c;自己也大三了#xff0c;时间真的有点紧啊w…刘汝佳的紫书差不多就告一段落吧我觉得可以了怎么说呢这书也陪着自己走了一年多了吧也目睹了从一个啥也不会的萌新到一个稍微会一点的萌新的转变。 差不多开始下本书吧自己也大三了时间真的有点紧啊woctm 最喜欢的图论作为自己对这本书的谢幕也好也好 uva10735欧拉回路网络流 题意给一个图图中有部分是向边部分是无向边要求判断是否存在欧拉回路若存在输出路径 解法 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define MEM(a,x) memset(a,x,sizeof(a)) 4 #define INF 0x3f3f3f3f 5 #define MAXN 10000106 using namespace std;7 8 struct Euler9 {10 struct Edge {11 int to, nxt;12 Edge() {}13 Edge(int x, int y) :to(x), nxt(y) {}14 }edges[MAXN];15 int head[MAXN], n, E;16 void init(const int n) {17 this-n n; E 0;18 for (int i 0; i n; i)head[i] -1;19 }20 void AddEdge(int f, int t) {21 edges[E] Edge(t, head[f]);22 head[f] E;23 }24 stackint S;25 bool vis[MAXN];//use when dfs26 void dfs(int x) {//get EulerCircle27 Edge e;28 for (int i head[x]; i ! -1; i e.nxt) {29 e edges[i];30 if (vis[i])continue;31 vis[i] 1;32 dfs(e.to);33 S.push(x);34 }35 }36 void getEulerCircle() {37 while (!S.empty())S.pop();38 memset(vis, 0, sizeof(vis));39 dfs(1);40 for (; !S.empty(); S.pop()) {41 printf(%d , S.top());42 }43 puts(1);44 }45 }gg;46 47 struct Dinic48 {49 struct Edge {50 int from, to, cap, flow;51 Edge(int u, int v, int c, int f) :52 from(u), to(v), cap(c), flow(f) {}53 };54 int n, s, t;55 vectorEdgeedges;56 vector intG[MAXN]; //gragh57 bool vis[MAXN]; //use when bfs58 int d[MAXN], cur[MAXN];//dist,now edge,use in dfs59 void AddEdge(int from, int to, int cap) {60 edges.push_back(Edge(from, to, cap, 0));61 edges.push_back(Edge(to, from, 0, 0));62 int top edges.size();63 G[from].push_back(top - 2);64 G[to].push_back(top - 1);65 }66 void init(int n, int s, int t) {67 this-n n;68 this-s s;69 this-t t;70 edges.clear();71 for (int i 0; i n; i)G[i].clear();72 }73 74 bool BFS() {75 memset(vis, 0, sizeof(vis));76 queueintQ;77 Q.push(s); d[s] 0; vis[s] 1;78 while (!Q.empty()) {79 int x Q.front(); Q.pop();80 for (int i 0; i G[x].size(); i) {81 Edge e edges[G[x][i]];82 if (vis[e.to] || e.cap e.flow)continue;83 vis[e.to] 1;84 d[e.to] d[x] 1;85 Q.push(e.to);86 }87 }88 return vis[t];89 }90 int DFS(const int x, int a) {91 if (x t || a 0) { return a; }92 int flow 0, f;93 for (int i cur[x]; i G[x].size(); i) {94 Edge e edges[G[x][i]];95 if (d[x] 1 ! d[e.to])continue;96 if ((f DFS(e.to, min(a, e.cap - e.flow))) 0)continue;97 e.flow f;98 edges[G[x][i] ^ 1].flow - f;//ϲߍ99 flow f; a - f;
100 if (!a) break;
101 }
102 return flow;
103 }
104 int MaxFlow(int s, int t) {
105 int flow 0;
106 for (; BFS();) {
107 memset(cur, 0, sizeof(cur));
108 flow DFS(s, INF);
109 }
110 return flow;
111 }
112 void buildEuler(int n) {
113 for (int i 1; i n; i) {
114 for (int j 0; j G[i].size(); j) {
115 Edge e edges[G[i][j]];
116 if (e.to s || e.to t) continue;
117 if (!e.cap)continue;
118 if (e.flow e.cap)gg.AddEdge(e.to, e.from);
119 else gg.AddEdge(e.from, e.to);
120 }
121 }
122 }
123 }g;
124
125 int d[MAXN];//degree out - in
126 bool work(int n) {
127 int flow 0;
128 REP(i, 1, n 1) {
129 if (d[i] 1)return 0;
130 if (d[i] 0) {
131 g.AddEdge(g.s, i, d[i] 1);
132 flow d[i] 1;
133 }
134 else if (d[i] 0)
135 g.AddEdge(i, g.t, -(d[i] 1));
136 }
137 if (flow ! g.MaxFlow(0, n 1)) return 0;
138 return 1;
139 }
140
141 int main() {
142 int T, x, y, n, m;
143 scanf(%d, T);
144 for (char ch; T--;) {
145 scanf(%d%d, n, m);
146 g.init(n, 0, n 1);
147 gg.init(n);
148 MEM(d, 0);
149 REP(i, 0, m) {
150 scanf(%d %d %c, x, y, ch);
151 if (ch D) gg.AddEdge(x, y);
152 else g.AddEdge(x, y, 1);
153 d[x]; d[y]--;//Degree
154 }
155 if (!work(n))puts(No euler circuit exist);
156 else {
157 g.buildEuler(n);
158 gg.getEulerCircle();
159 }
160 if (T)puts();
161 }
162 return 0;
163 } uva1001 题意 给出一些球球内的时间为零球之间的速度为10每单位。给两个点求最短时间。 解法 处理出任意两点之间的距离 做题的时候要大胆点hhh 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define MEM(a,x) memset(a,x,sizeof(a)) 4 #define INF 0x3f3f3f3f 5 #define MAXN 100106 using namespace std;7 struct node { int x, y, z, r; }p[MAXN];8 double g[MAXN][MAXN];9
10 double dis(node a,node b) {
11 double ans sqrt(
12 (a.x - b.x)*(a.x - b.x)
13 (a.y - b.y)*(a.y - b.y)
14 (a.z - b.z)*(a.z - b.z))
15 - (a.r b.r);
16 return ans 0 ? 0 : ans;
17 }
18
19 int main() {
20 int n, cnt 0;
21 while (cin n n ! -1) {
22 REP(i, 0, n) cin p[i].x p[i].y p[i].z p[i].r;
23 cin p[n].x p[n].y p[n].z; p[n].r 0;
24 cin p[n 1].x p[n 1].y p[n 1].z; p[n 1].r 0;
25
26 MEM(g, INF);
27 REP(i, 0, n 2)g[i][i] 0;
28 REP(i, 0, n 2)REP(j, 0, n 2) g[i][j] dis(p[i], p[j]);
29
30 REP(k, 0, n 2)REP(i, 0, n 2)REP(j, 0, n 2)
31 g[i][j] min(g[i][j], g[i][k] g[k][j]);
32
33 g[n][n 1] * 10;
34 printf(Cheese %d: Travel time %.0f sec\n, cnt, g[n][n 1]);
35 }
36 return 0;
37 } uva820 题意有一个计算机网络输入节点数n输入网络流源点和汇点srcdes再输入双向边数m。给出m条边的负载求最大流。 解法 网络流模板题 你想流量其实就是运输物品我们要求的就是从源点到汇点最多能运输多少单位的物品 当物品变成水流的时候他可以均匀的分布在所有边上每个边上可以有的物品数就是这个边的容量所有可行边的路径和就是我们要求的所谓“路径权值和” 这道题Dinic中的init有问题改了一下就好了 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define MEM(a,x) memset(a,x,sizeof(a)) 4 #define INF 0x3f3f3f3f 5 #define MAXN 1000106 using namespace std;7 struct Edge {8 int from, to, cap, flow;9 };
10 struct Dinic {
11 int n, m, s, t;
12 vectorEdgeedges;
13 vectorintG[MAXN];
14 bool vis[MAXN];
15 int d[MAXN];
16 int cur[MAXN];
17 void init() {
18 edges.clear();
19 for (int i 0; i MAXN; i) G[i].clear();
20 memset(d, 0, sizeof d);
21 }
22 void AddEdge(int from, int to, int cap) {
23 edges.push_back({ from, to, cap, 0 });
24 edges.push_back({ to, from, 0, 0 });
25 m edges.size();
26 G[from].push_back(m - 2);
27 G[to].push_back(m - 1);
28 }
29 bool BFS() {
30 int x, i;
31 memset(vis, 0, sizeof(vis));
32 queueintQ;
33 Q.push(s);
34 d[s] 0;
35 vis[s] 1;
36 while (!Q.empty()) {
37 x Q.front(), Q.pop();
38 for (i 0; i G[x].size(); i) {
39 Edge e edges[G[x][i]];
40 if (!vis[e.to] e.cap e.flow) {
41 vis[e.to] 1;
42 d[e.to] d[x] 1;
43 Q.push(e.to);
44 }
45 }
46 }
47 return vis[t];
48 }
49 int DFS(int x, int a) {
50 if (x t || a 0)
51 return a;
52 int flow 0, f;
53 for (int i cur[x]; i G[x].size(); i) {
54 Edge e edges[G[x][i]];
55 if (d[x] 1 d[e.to] (f DFS(e.to, min(a, e.cap - e.flow))) 0) {
56 e.flow f;
57 edges[G[x][i] ^ 1].flow - f;
58 flow f;
59 a - f;
60 if (a 0)
61 break;
62 }
63 }
64 return flow;
65 }
66 int Maxflow(int s, int t) {
67 this-s s, this-t t;
68 int flow 0;
69 while (BFS()) {
70 memset(cur, 0, sizeof(cur));
71 flow DFS(s, INF);
72 }
73 return flow;
74 }
75 }Men;
76 int main() {
77 int n, kase 0;
78 while (scanf(%d, n) n) {
79 int s, t, c, u, v, w;
80 Men.init();
81 scanf(%d%d%d, s, t, c);
82 REP(i, 0, c) {
83 scanf(%d%d%d, u, v, w);
84 Men.AddEdge(u, v, w);
85 Men.AddEdge(v, u, w);
86 }
87 printf(Network %d\nThe bandwidth is %d.\n\n, kase, Men.Maxflow(s, t));
88 }
89 return 0;
90 } uva10801 题意 一个人在大楼的0楼大楼最多到99层。有n部电梯每部电梯有可到达的楼层每个电梯移动一层的时间为T[i]秒。换电梯的时间为60秒。 给你一个楼层问你电梯到这个楼层的最短路径。 解法 很容易看出是一个最短路问题关键在于如何建图 首先我们分析一下我们很容易想到把楼层当作点把时间当左边但是有一个问题由于它涉及楼层中换电梯所以这样做的话我们就无法计算换电梯的时间所以我的方法是把一个楼层拆成n个点这样做的前提是在这道题中n比较小5分别表示从哪一个电梯下来的。然后再把相同楼层的点之间加一条长度为60的边。 这样再通过执行n次Dijkstra算法去最小值得出答案。或者直接Floyd 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define MEM(a,x) memset(a,x,sizeof(a)) 4 #define INF 0x3f3f3f3f 5 #define MAXN 100106 using namespace std;7 int t[MAXN], num[MAXN];8 int g[MAXN][MAXN];9
10 void AddEdge(int i, int j, int s) {
11 g[i][j] g[j][i] min(min(g[i][j], g[j][i]), abs(i - j)*s);
12 return;
13 }
14
15 int main() {
16 int n, k;
17 while (scanf(%d%d, n, k) ! EOF) {
18 MEM(g, INF);
19 REP(i, 0, n)scanf(%d, t[i]);
20 int UP -1;
21 REP(i, 0, n) {
22 char ch \0;
23 for (int j 0; ch ! \n; j) {
24 scanf(%d%c, num[j], ch);
25 UP max(UP, num[j]);
26 REP(k, 0, j) AddEdge(num[j], num[k], t[i]);
27 }
28 }
29
30 UP;
31 REP(i, 0, UP)g[i][i] 0;
32 REP(k, 0, UP)REP(i, 0, UP)REP(j, 0, UP)
33 g[i][j] min(g[i][j], g[i][k] g[k][j] 60);
34
35 if (k 0)printf(0\n);
36 else if (g[0][k] INF)printf(IMPOSSIBLE\n);
37 else printf(%d\n, g[0][k]);
38 }
39 return 0;
40 } uva1663 题意 给出一些01串含星号的串表示包含两个串星号位置分别为0和1。 每次可以消掉一个串或者两个只有一个数字不同的串求最少几次可以消掉所有串。 解法 读出所有串两两判断能否一起消掉然后其最大匹配数即可。具体细节见代码。 这道题的建图挺有意思的 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define CLR(a) memset(a,0,sizeof(a));4 #define MEM(a,x) memset(a,x,sizeof(a)) 5 #define ALL(x) begin(x),end(x)6 #define INF 0x3f3f3f3f 7 #define MAXN 2000108 #define LL long long9 using namespace std;
10
11 int Set[MAXN], n, m;
12 char s[20];
13
14 int g[MAXN][MAXN], match[MAXN], vis[MAXN];
15 bool dfs(int u) {
16 for (int i 0; i MAXN; i) {
17 if (g[u][i] !vis[i]) {
18 vis[i] 1;
19 if (match[i] -1 || dfs(match[i])) {
20 match[i] u;
21 return true;
22 }
23 }
24 }
25 return false;
26 }
27
28 int Hungarian(){
29 int ans 0;
30 memset(match, -1, sizeof(match));
31 for (int i 0; i MAXN; i){
32 memset(vis, 0, sizeof(vis));
33 if (dfs(i))ans;
34 }
35 return ans;
36 }
37
38 int main() {
39 while (scanf(%d%d, n, m) (nm)) {
40 CLR(g); CLR(Set); CLR(vis);
41 REP(i, 0, m) {
42 scanf(%s, s);
43 int pos -1, tmp 0;
44 REP(j, 0, n) {
45 if (s[j] 1)tmp | 1 j;
46 else if (s[j] *)pos j;
47 }
48 Set[tmp] 1;
49 if (pos ! -1) {//将*拆分成0和1两种
50 tmp | 1 pos;
51 Set[tmp] true;
52 }
53 }
54 m 0;
55 REP(i, 0, MAXN) {
56 if (Set[i]) {
57 m;
58 REP(j, 0, n) {
59 int tmp i ^ (1 j);//只有一位不同
60 if (Set[tmp])g[i][tmp] true;
61 }
62 }
63 }
64 printf(%d\n, m - Hungarian() / 2);
65 }
66 return 0;
67 } uva12549 题意 在一个Y行X列的网格里有空地.重要位置*和障碍物#用最少的机器人看守所有重要位置每个机器人要放在一个格子里面朝上下左右4个方向之一。 机器人会发出激光一直射到障碍物为止沿途都是看守范围。 解法 首先肯定是二分图最大匹配其次如果没有障碍物的话直接每个目标的x和y建表跑匈牙利即可 但这个题目中他有障碍物我们就横纵坐标分块即可相当于离散化之后匈牙利 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define CLR(a) memset(a,0,sizeof(a));4 #define MEM(a,x) memset(a,x,sizeof(a)) 5 #define ALL(x) begin(x),end(x)6 #define INF 0x3f3f3f3f 7 #define MAXN 100108 #define MAXM 20059 #define LL long long
10 using namespace std;
11
12 int g[MAXM][MAXM], match[MAXM], vis[MAXM];
13 int mp[MAXN][MAXN], X[MAXN][MAXN], Y[MAXN][MAXN];
14 int xcnt, ycnt;
15 bool dfs(int u) {
16 for (int i 0; i ycnt; i) {
17 if (g[u][i] !vis[i]) {
18 vis[i] 1;
19 if (match[i] -1 || dfs(match[i])) {
20 match[i] u;
21 return true;
22 }
23 }
24 }
25 return false;
26 }
27
28 int Hungarian() {
29 int ans 0;
30 memset(match, -1, sizeof(match));
31 for (int i 0; i xcnt; i) {
32 memset(vis, 0, sizeof(vis));
33 if (dfs(i))ans;
34 }
35 return ans;
36 }
37
38 int main() {
39 int T; scanf(%d, T);
40 while (T--) {
41 CLR(g); CLR(mp); CLR(X); CLR(Y);
42 getchar();
43 int n, m; scanf(%d%d, n, m);
44
45 int p, x, y;
46 scanf(%d, p);
47 REP(i, 0, p) { scanf(%d %d, x, y); mp[x-1][y-1] 1; }
48 scanf(%d, p);
49 REP(i, 0, p) { scanf(%d %d, x, y); mp[x-1][y-1] 2; }
50
51 xcnt -1;
52 REP(i, 0, n) {
53 bool flag true;
54 REP(j, 0, m) {
55 if (mp[i][j] 1) {
56 if (flag)xcnt;
57 X[i][j] xcnt;
58 flag false;
59 }
60 else if(mp[i][j]2)
61 flag true;
62 }
63 }
64 ycnt -1;
65 REP(i, 0, n) {
66 bool flag true;
67 REP(j, 0, m) {
68 if (mp[j][i] 1) {
69 if (flag)ycnt;
70 Y[j][i] ycnt;
71 flag false;
72 }
73 else if (mp[j][i] 2)
74 flag true;
75 }
76 }
77 xcnt, ycnt;
78
79 REP(i, 0, n)REP(j, 0, m)if(mp[i][j]1)
80 g[X[i][j]][Y[i][j]] 1;
81 printf(%d\n, Hungarian());
82 }
83 return 0;
84 } uva1664 题意 给你n个点接着给你n-1条边形成一颗生成树每条边都有一个权值。 求的是以一个点作为特殊点并求出从此点出发到其他每个点的条件边权的总和最大条件边权就是起点到终点经过的权值的最小值。 解法 非常巧妙的并查集真的没有想到 首先我们把要选的那个结点看作是我们的根节点用Kruscal的思想首先给所有边按照从大到小的顺序排序 之后我们遍历每条边该边的两个顶点所在的集合设为A、B集合A、B的顶点a、b要让谁当中心点呢 易知无论谁当中心点它与另一个集合中任一点的容量都为该边长度因为是从大到小枚举的。 那么为了求出总容量我们要维护一些值用空间换时间 。 维护每个顶点的总容量sum[i]维护每个顶点与之相连的顶点数量cnt[i]当前答案ans 。 那么对于a、b点如果以a为中心总容量为sum[a] cnt[b] * e[i].c 。 反之亦然哪个量大则以哪个点为城市中心也就是并查集的根结点 。 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define CLR(a) memset(a,0,sizeof(a));4 #define MEM(a,x) memset(a,x,sizeof(a)) 5 #define ALL(x) begin(x),end(x)6 #define LL long long7 const int INF 0x3f3f3f3f;8 const int MAXN 200000 10;9 using namespace std;
10
11 struct edge {
12 int u, v, w;
13 bool operator (const edge rhs) const {
14 return w rhs.w;
15 }
16 }e[MAXN];
17 LL p[MAXN], sum[MAXN], cnt[MAXN];
18 int findSet(int x) { return p[x] x ? x : p[x] findSet(p[x]); }
19 int main() {
20 int n;
21 while (scanf(%d, n) ! EOF) {
22 REP(i, 0, n - 1) {scanf(%d%d%d, e[i].u, e[i].v, e[i].w);}
23 REP(i, 1, n1) {p[i] i; sum[i] 0; cnt[i] 1;}
24 sort(e, e n - 1);
25 LL ans 0;
26 REP(i, 0, n - 1) {
27 int x findSet(e[i].u), y findSet(e[i].v);
28 LL sumu sum[x] cnt[y] * e[i].w;
29 LL sumv sum[y] cnt[x] * e[i].w;
30 if (sumu sumv) {
31 p[x] y; cnt[y] cnt[x];
32 ans sum[y] sumv;
33 }
34 else {
35 p[y] x; cnt[x] cnt[y]; sum[x] sumu;
36 ans sum[x] sumu;
37 }
38 }
39 printf(%lld\n, ans);
40 }
41 return 0;
42 } uva1668建图 题意 给定一棵有 nn 个节点的树每条边有边权 w(u,v)w(u,v)用最小的路径覆盖所有的边使得每条边被覆盖的次数等于其边权。 解法 这道题考的是思维。 首先我们求出所有点的权值之和就是我们要求的答案的最大值再求出每个点的最大权值依次看其是否超过总权值的一半 如果超过的话我们就直接减去最大权值代表不能全部合并 否则我们就减去总权值的一半代表能全部合并 1 #includebits/stdc.h2 #define REP(i, a, b) for(int i (a); i (b); i)3 #define CLR(a) memset(a,0,sizeof(a));4 #define MEM(a,x) memset(a,x,sizeof(a)) 5 #define ALL(x) begin(x),end(x)6 #define LL long long7 #define INF 0x3f3f3f3f8 #define MAXN 100000 109 using namespace std;
10
11 int deg[MAXN], maxd[MAXN];
12 int main() {
13 int T; scanf(%d, T);
14 int kase 0;
15 while (T--) {
16 CLR(deg); CLR(maxd);
17 int n; scanf(%d, n);
18 int u, v, w;
19 LL ans 0;
20 REP(i, 1, n) {
21 scanf(%d%d%d, u, v, w);
22 deg[u] w, deg[v] w;
23 maxd[u] max(maxd[u], w);
24 maxd[v] max(maxd[v], w);
25 ans w;
26 }
27 REP(i, 1, n1) {
28 if ((maxd[i] 1) deg[i])
29 ans - deg[i] 1;
30 else
31 ans - deg[i] - maxd[i];
32 }
33 printf(Case #%d: %lld\n, kase, ans);
34 }
35 return 0;
36 } 转载于:https://www.cnblogs.com/romaLzhih/p/9661331.html
