白银市建设局网站首页,怎么做网站互换链接,企业宣传片拍摄脚本,牛商网做网站要多少钱题意#xff1a;给你无向图#xff0c;给定一条边#xff0c;求至少在原图中删去多少边才能使它同时在某个最大生成树和某个最小生成树中。 解#xff1a; 假装我们把边排序了#xff0c;然后把所有边权小于给定边的边都加进去了。 那么我们要删的就是s到t的一个割。 最大…题意给你无向图给定一条边求至少在原图中删去多少边才能使它同时在某个最大生成树和某个最小生成树中。 解 假装我们把边排序了然后把所有边权小于给定边的边都加进去了。 那么我们要删的就是s到t的一个割。 最大同理。 然后我们做两遍最小割即可。 注意边权与给定边相等的边直接忽略。 1 #include cstdio2 #include algorithm3 #include queue4 #include cstring5 6 const int N 20010, M 1000010, INF 0x3f3f3f3f;7 const int dx[] {1, 0, -1, 0};8 const int dy[] {0, 1, 0, -1};9 10 struct Edge {11 int nex, v, c;12 }edge[M 1]; int top 1;13 14 struct Eg {15 int u, v, len;16 inline bool operator (const Eg w) const {17 return len w.len;18 }19 }eg[M];20 21 int e[N], d[N];22 std::queueint Q;23 24 inline void add(int x, int y, int z) {25 top;26 edge[top].v y;27 edge[top].c z;28 edge[top].nex e[x];29 e[x] top;30 31 top;32 edge[top].v x;33 edge[top].c z;34 edge[top].nex e[y];35 e[y] top;36 return;37 }38 39 inline bool BFS(int s, int t) {40 memset(d, 0, sizeof(d));41 d[s] 1;42 Q.push(s);43 while(!Q.empty()) {44 int x Q.front();45 Q.pop();46 for(int i e[x]; i; i edge[i].nex) {47 int y edge[i].v;48 if(!edge[i].c || d[y]) {49 continue;50 }51 d[y] d[x] 1;52 Q.push(y);53 }54 }55 return d[t];56 }57 58 int DFS(int x, int t, int maxF) {59 if(x t) {60 return maxF;61 }62 int ans 0;63 for(int i e[x]; i; i edge[i].nex) {64 int y edge[i].v;65 if(!edge[i].c || d[x] 1 ! d[y]) {66 continue;67 }68 int temp DFS(y, t, std::min(edge[i].c, maxF - ans));69 if(!temp) {70 d[y] INF;71 }72 ans temp;73 edge[i].c - temp;74 edge[i ^ 1].c temp;75 if(ans maxF) {76 break;77 }78 }79 return ans;80 }81 82 inline int solve(int s, int t) {83 int ans 0;84 while(BFS(s, t)) {85 ans DFS(s, t, INF);86 }87 return ans;88 }89 90 int main() {91 int n, m, L, s, t;92 scanf(%d%d, n, m);93 for(int i 1; i m; i) {94 scanf(%d%d%d, eg[i].u, eg[i].v, eg[i].len);95 }96 scanf(%d%d%d, s, t, L);97 std::sort(eg 1, eg m 1);98 int i;99 for(i 1; i m; i) {
100 if(eg[i].len L) {
101 break;
102 }
103 add(eg[i].u, eg[i].v, 1);
104 }
105 int ans solve(s, t);
106 memset(e, 0, sizeof(e));
107 top 1;
108 for(; i m; i) {
109 if(eg[i].len L) {
110 continue;
111 }
112 add(eg[i].u, eg[i].v, 1);
113 }
114 printf(%d, ans solve(s, t));
115 return 0;
116 } AC代码 一开始我想把两遍最小割合成一遍后来发现不行。 比如这个样例 3 2 1 2 1 2 3 3 1 3 2 最小删边是0但是一次最小割是1。 思考会不会有这种情况你删掉一个比给定边小的边使得最大生成树无法达成(图不连通) 应该不会因为你两次割的互不影响且都成环。转载于:https://www.cnblogs.com/huyufeifei/p/10110881.html
