PDF《介绍 0》

i < n;

i++) d[i] = INF;

memset(inq, false, sizeof(inq));

d[s] = 0;

inq[s] = true;

p[s] = 0;

a[s] = INF;

int front, rear;

Q[rear = front = 0] = s;

while (front e.flow && d[e.v] > d[u] + e.cost) { d[e.v] = d[u] + e.cost;

p[e.v] = i;

a[e.v] = min(a[u], e.cap - e.flow);

if (!inq[e.v]) {Q[++rear] = e.v;

inq[e.v] = if (d[t] == INF) return false;

flow += a[t];

cost += d[t] * a[t];

int u = t;

while (u != s) { edges[p[u]].flow += a[t];

图论

75 First Chapter edges[p[u]^1].flow -= a[t];

u = edges[p[u]].u;

return true;

} Type Mincost(int s, int t) { Type flow = 0, cost = 0;

while (BellmanFord(s, t, flow, cost));

return cost;

} }H;

int mapp[610][610];

int main() { int n, u, v, w;

freopen("in.txt", "r", stdin);

while (scanf("%d", &n) != EOF) { for (int i = 0;

i < n;

i++) for (int j = 0;

j < n;

j++) scanf("%d", &mapp[i][j]);

int s = 0, t = 2*n*n-1;

H.init(t+1);

for (int i = 0;

i < n;

i++) { for (int j = 0;

j < n;

j++) { H.AddEdge(i*n+j, i*n+j+n*n, 1, -mapp[i][j]);

if (j != n-1) H.AddEdge(i*n+j+n*n, i*n+j+1, 1, 0);

if (i != n-1) H.AddEdge(i*n+j+n*n, i*n+j+n, 1, 0);

H.AddEdge(s, n*n, 1, 0);

H.AddEdge(n*n-1, t, 1, 0);

printf("%d\n", -H.Mincost(s, t));

图论

76 First Chapter } return 0;

} hdu

3718 Similarity 给出A, B两个分别由k不同字符组成的长度相同的字符串,现在把B中的每种字符 变成A中含有的某种字符,(不能变成相同的A),求最多能有多少个字符匹配. #include #include #include using namespace std;

typedef int Type;

const int maxv = 1e+5;

const int maxe = 1e+7;

const int INF = 0x3f3f3f3f;

struct Edge { int u, v;

Type cap, flow, cost;

Edge() {} Edge(int u, int v, Type cap, Type flow, Type cost) { this->u = u;

this->v = v;

this->cap = cap;

this->flow = flow;

this->cost = cost;

} };

struct MCFC { int n, m, s, t;

Edge edges[maxe];

图论

77 First Chapter int first[maxv];

int next[maxe];

int inq[maxv];

Type d[maxv];

int p[maxv];

Type a[maxv];

int Q[maxe];

void init(int n) { this->n = n;

memset(first, -1, sizeof(first));

m = 0;

} void AddEdge(int u, int v, Type cap, Type cost) { edges[m] = Edge(u, v, cap, 0, cost);

next[m] = first[u];

first[u] = m++;

edges[m] = Edge(v, u, 0, 0, -cost);

next[m] = first[v];

first[v] = m++;

} bool BellmanFord(int s, int t, Type &flow, Type &cost) for (int i = 0;

i < n;

i++) d[i] = INF;

memset(inq, false, sizeof(inq));

d[s] = 0;

inq[s] = true;

p[s] = 0;

a[s] = INF;

int front, rear;

Q[rear = front = 0] = s;

while (front e.flow && d[e.v] > d[u] + e.cost) { 图论

78 First Chapter d[e.v] = d[u] + e.cost;

p[e.v] = i;

a[e.v] = min(a[u], e.cap - e.flow);

if (!inq[e.v]) {Q[++rear] = e.v;

inq[e.v] = if (d[t] == INF) return false;

flow += a[t];

cost += d[t] * a[t];

int u = t;

while (u != s) { edges[p[u]].flow += a[t];

edges[p[u]^1].flow -= a[t];

u = edges[p[u]].u;

return true;

} Type Mincost(int s, int t) { Type flow = 0, cost = 0;