哪里有网站培训的,怎么做网站的内链,建设项目环保验收公示网站,网站建设设计工具题意 有一个图#xff0c; 两种操作#xff0c;一种是删除某点的所有出边#xff0c;一种是删除某点的所有入边#xff0c;各个点的不同操作分别有一个花费#xff0c;现在我们想把这个图的边都删除掉#xff0c;需要的最小花费是多少。 思路 很明显的二分图最小点权覆盖…题意 有一个图 两种操作一种是删除某点的所有出边一种是删除某点的所有入边各个点的不同操作分别有一个花费现在我们想把这个图的边都删除掉需要的最小花费是多少。 思路 很明显的二分图最小点权覆盖集。WA在输出最小割方案上。 【输出最小割方案】从源点S做一次DFS遍历标记所有访问到的点这些点就是S点集。然后对于每一条满流边如果其两端点一个在S点集一个不在则该边就是此方案下的最小割边。 代码 [cpp] #include iostream #include cstdio #include cmath #include vector #include algorithm #include string #include cstring #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, m) for (int i begin; i beginm; i ) using namespace std; const int MAXV 205; const int MAXE 10005; const int oo 0x3fffffff; template typename T struct Dinic{ struct flow_node{ int u, v; T flow; int opp; int next; }arc[2*MAXE]; int vn, en, head[MAXV]; int cur[MAXV]; int q[MAXV]; int path[2*MAXE], top; int dep[MAXV]; void init(int n){ vn n; en 0; MEM(head, -1); } void insert_flow(int u, int v, T flow){ arc[en].u u; arc[en].v v; arc[en].flow flow; arc[en].next head[u]; head[u] en ; arc[en].u v; arc[en].v u; arc[en].flow 0; arc[en].next head[v]; head[v] en ; } bool bfs(int s, int t){ MEM(dep, -1); int lq 0, rq 1; dep[s] 0; q[lq] s; while(lq rq){ int u q[lq ]; if (u t){ return true; } for (int i head[u]; i ! -1; i arc[i].next){ int v arc[i].v; if (dep[v] -1 arc[i].flow 0){ dep[v] dep[u] 1; q[rq ] v; } } } return false; } T solve(int s, int t){ T maxflow 0; while(bfs(s, t)){ int i, j; for (i 1; i vn; i ) cur[i] head[i]; for (i s, top 0;;){ if (i t){ int mink; T minflow 0x7fffffff; //要比容量的oo大 for (int k 0; k top; k ) if (minflow arc[path[k]].flow){ minflow arc[path[k]].flow; mink k; } for (int k 0; k top; k ) arc[path[k]].flow - minflow, arc[path[k]^1].flow minflow; maxflow minflow; top mink; i arc[path[top]].u; } for (j cur[i]; j ! -1; cur[i] j arc[j].next){ int v arc[j].v; if (arc[j].flow dep[v] dep[i] 1) break; } if (j ! -1){ path[top ] j; i arc[j].v; } else{ if (top 0) break; dep[i] -1; i arc[path[-- top]].u; } } } return maxflow; } }; Dinic int dinic; vector pairint, char res; bool vis[MAXV]; void dfs(int u){ vis[u] true; for (int i dinic.head[u]; i ! -1; i dinic.arc[i].next){ if (dinic.arc[i].flow 0) continue; int v dinic.arc[i].v; if (!vis[v]){ dfs(v); } } } int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); int n, m; while(scanf(%d %d, n, m) ! EOF){ dinic.init(2*n2); REP(i, 1, n){ int tmp; scanf(%d, tmp); dinic.insert_flow(in, 2*n2, tmp); } REP(i, 1, n){ int tmp; scanf(%d, tmp); dinic.insert_flow(2*n1, i, tmp); } REP(i, 1, m){ int u, v; scanf(%d %d, u, v); dinic.insert_flow(u, vn, oo); } printf(%d\n, dinic.solve(2*n1, 2*n2)); res.clear(); MEM(vis, 0); dfs(2*n1); for (int i 0; i dinic.en; i ){ if (dinic.arc[i].u 2*n1 dinic.arc[i].flow 0){ if (!vis[dinic.arc[i].v]) res.push_back(make_pair(dinic.arc[i].v, -)); } if (dinic.arc[i].v 2*n2 dinic.arc[i].flow 0){ if (vis[dinic.arc[i].u]) res.push_back(make_pair(dinic.arc[i].u - n, )); } } printf(%d\n, (int)res.size()); for (int i 0; i (int)res.size(); i ){ printf(%d %c\n, res[i].first, res[i].second); } } return 0; } [/cpp]转载于:https://www.cnblogs.com/AbandonZHANG/p/4114303.html
