网络流应用 I
前言
被两个并不看正文的同学追着更新….emmmm…..
本文不写题意不写思路只给代码，一切内容都在以下PKU的课件中
（PS：膜拜神犇们的构图 orz）
Optimal Milking - POJ 2112
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 250;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, next;
edge(int pv, int pval, int pnext): v(pv), val(pval), next(pnext) {}
edge() {}
};
edge e[N*N*2];
int tot, head[N], pre[N], d[N], cur[N], gap[N];
int G[N][N];
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int val){
e[tot] = edge(v, val, head[u]);
head[u] = tot++;
e[tot] = edge(u, 0, head[v]);
head[v] = tot++;
}
void floyd(int n){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
}
}
void build(int k, int c, int m, int maxdist){
for(int i = k + 1; i <= k + c; i++) addEdge(0, i, 1);
for(int i = 1; i <= k; i++) addEdge(i, k + c + 1, m);
for(int i = k + 1; i <= k + c; i++){
for(int j = 1; j <= k; j++){
if(G[i][j] <= maxdist) addEdge(i, j, 1);
}
}
}
int ISAP(int src, int des, int n){
memcpy(cur, head, sizeof(head));
memset(gap, 0, sizeof(gap));
memset(d, 0, sizeof(d));
int u = pre[src] = src;
int sum = 0;
gap[0] = n;
while(d[src] < n){
if(u == des){
int v, aug = inf;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val -= aug;
e[cur[u]^1].val += aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
int main(){
int k, c, m;
while(~scanf("%d%d%d", &k, &c, &m)){
for(int i = 1; i <= k + c; i++){
for(int j = 1; j <= k + c; j++){
scanf("%d", &G[i][j]);
if(G[i][j] == 0) G[i][j] = inf;
}
}
floyd(k + c);
int l = 0, r = 60000, ans;
while(l <= r){
int mid = (l + r) >> 1;
init();
build(k, c, m, mid);
if(ISAP(0, k + c + 1, k + c + 2) == c){
ans = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
printf("%d\n", ans);
}
}
ACM Computer Factory - POJ 3436
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 50 + 15;
const int M = 1e4 + 15;
const int P = 10 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, flow, cap, nxt;
edge(int pv, int pflow, int pcap, int pnxt): v(pv), flow(pflow), cap(pcap), nxt(pnxt) {}
edge() {}
};
int d[N], head[N], gap[N], cur[N], pre[N];
edge e[M << 1];
int tot;
int from[N][P], to[N][P], val[N];
vector<int> ansu, ansv, ansflow;
inline void init(){
memset(head, -1, sizeof(head));
memset(d, 0, sizeof(d));
memset(gap, 0, sizeof(gap));
tot = 0;
ansu.clear();
ansv.clear();
ansflow.clear();
}
void addEdge(int u, int v, int val){
e[tot] = edge(v, 0, val, head[u]);
head[u] = tot++;
e[tot] = edge(u, val, val, head[v]);
head[v] = tot++;
}
bool can(int i, int j, int p){
for(int k = 0; k < p; k++){
if(from[i][k] == 2) continue;
if(from[i][k] != to[j][k]) return false;
}
return true;
}
void buildG(int n, int p){
for(int i = 0; i < n; i++){
bool flag = true;
for(int j = 0; j < p; j++){
if(from[i][j] == 1){
flag = false;
break;
}
}
if(flag) addEdge(0, i + 1, inf);
}
for(int i = 0; i < n; i++){
addEdge(i + 1, i + 1 + n, val[i]);
}
for(int i = 0; i < n; i++){
bool flag = true;
for(int j = 0; j < p; j++){
if(to[i][j] == 0){
flag = false;
break;
}
}
if(flag) addEdge(i + 1 + n, n << 1 | 1, inf);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(can(i, j, p)){
addEdge(j + n + 1, i + 1, inf);
}
}
}
}
int ISAP(int n, int src, int des){
memcpy(cur, head, sizeof(head));
int sum = 0;
int u = pre[src] = src;
gap[0] = n;
while(d[src] < n){
if(u == des){
int aug = inf, v;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].cap - e[cur[u]].flow);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].flow += aug;
e[cur[u]^1].flow -= aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].cap - e[i].flow > 0){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(e[i].cap - e[i].flow > 0 && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
void getAns(int n){
for(int i = 0; i < tot; i += 2){
if(e[i].flow > 0){
int u = e[i^1].v;
int v = e[i].v;
if(u > n && v <= n){
ansu.push_back(u - n);
ansv.push_back(v);
ansflow.push_back(e[i].flow);
}
}
}
}
int main(){
int p, n;
while(~scanf("%d%d", &p, &n)){
init();
for(int i = 0; i < n; i++){
scanf("%d", &val[i]);
for(int j = 0; j < p; j++) scanf("%d", &from[i][j]);
for(int j = 0; j < p; j++) scanf("%d", &to[i][j]);
}
buildG(n, p);
int maxx = ISAP(2*n + 2, 0, 2*n + 1);
getAns(n);
printf("%d %d\n", maxx, ansu.size());
for(int i = 0; i < ansu.size(); i++){
printf("%d %d %d\n", ansu[i], ansv[i], ansflow[i]);
}
}
}
PIGS - POJ 1149
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, next;
edge(int pv, int pval, int pnext): v(pv), val(pval), next(pnext) {}
edge() {}
};
edge e[N*N*2];
int tot, head[N], pre[N], d[N], cur[N], gap[N];
int val[N], mp[N];
inline void init(){
memset(head, -1, sizeof(head));
memset(mp, -1, sizeof(mp));
tot = 0;
}
inline void addEdge(int u, int v, int val){
e[tot] = edge(v, val, head[u]);
head[u] = tot++;
e[tot] = edge(u, 0, head[v]);
head[v] = tot++;
}
int ISAP(int src, int des, int n){
memcpy(cur, head, sizeof(head));
memset(gap, 0, sizeof(gap));
memset(d, 0, sizeof(d));
int u = pre[src] = src;
int sum = 0;
gap[0] = n;
while(d[src] < n){
if(u == des){
int v, aug = inf;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val -= aug;
e[cur[u]^1].val += aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i <= m; i++){
int k, dist;
scanf("%d", &k);
while(k--){
int tmp;
scanf("%d", &tmp);
if(mp[tmp] == -1){
mp[tmp] = i;
addEdge(0, mp[tmp], val[tmp]);
}else{
addEdge(mp[tmp], i, inf);
mp[tmp] = i;
}
}
scanf("%d", &dist);
addEdge(i, m + 1, dist);
}
printf("%d\n", ISAP(0, m + 1, m + 2));
}
}
