# HDU 3879 && BZOJ 1497：Base Station && 最大获利 （最大权闭合图）

2022年11月23日
0 收藏 463 点赞 4,765 浏览 2233 个字

http://acm.hdu.edu.cn/showproblem.php?pid=3879

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

` #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define INF 0x3f3f3f3f #define N 60010 #define M 350010 // 30w不过 struct Edge {     int u, v, nxt, cap;     Edge () {}     Edge (int u, int v, int nxt, int cap) : u(u), v(v), nxt(nxt), cap(cap) {} } edge[M]; int head[N], tot, S, T, cur[N], dis[N], gap[N], pre[N]; void Add(int u, int v, int cap) {     edge[tot] = Edge(u, v, head[u], cap); head[u] = tot++;     edge[tot] = Edge(v, u, head[v], ); head[v] = tot++; } void BFS() {     queue<int> que;     que.push(T);     memset(dis, INF, sizeof(dis));     memset(gap, , sizeof(gap));     gap[]++; dis[T] = ;     while(!que.empty()) {         int u = que.front(); que.pop();         for(int i = head[u]; ~i; i = edge[i].nxt) {             if(dis[edge[i].v] != INF) continue;             dis[edge[i].v] = dis[u] + ;             gap[dis[edge[i].v]]++;             que.push(edge[i].v);         }     } } int ISAP(int n) {     BFS();     memcpy(cur, head, sizeof(cur));     int u = pre[S] = S, flow, ans = , index, i;     while(dis[S] < n) {         if(u == T) {             flow = INF;             for(i = S; i != T; i = edge[cur[i]].v)                 if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;             for(i = S; i != T; i = edge[cur[i]].v)                 edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;             u = index; ans += flow;         }         for(i = cur[u]; ~i; i = edge[i].nxt) if(edge[i].cap && dis[edge[i].v] +  == dis[u]) break;         if(~i) { cur[u] = i; pre[edge[i].v] = u; u = edge[i].v; }         else {             if(--gap[dis[u]] == ) break;             int md = n + ;             for(i = head[u]; ~i; i = edge[i].nxt)                 if(edge[i].cap && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;             gap[dis[u] = md + ]++;             u = pre[u];         }     }     return ans; } int main() {     int n, m;     while(~scanf("%d%d", &n, &m)) {         memset(head, -, sizeof(head));         tot = ; S = ; T = n + m + ;         for(int i = ; i <= n; i++) {             int w; scanf("%d", &w);             Add(S, i, w); // 源点和站点相连         }         int tot = ;         for(int i = ; i <= m; i++) {             int a, b, c;             scanf("%d%d%d",&a, &b, &c);             tot += c; // 选择边的利润和             Add(i + n, T, c); // 边的点和汇点相连             Add(a, i + n, INF);             Add(b, i + n, INF);         }         printf("%d\n", tot - ISAP(T + ));     }     return ; }`

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com