2016-10-01

HDU 5772 String problem【最大权闭合子图】

题意：

给定长度为$n$的由数字组成的序列，给定收益和花费的函数，现求一个子序列，使得其收益-花费最大。
数据范围：$0 \le n \le 100$

分析：

官方题解说的非常清楚了，通过这题理解最大权闭合子图，写这道题题解的目的一是觉得建图以及处理那里比较巧妙，二是纪念我因为网络流$vector$清空时$maxm$误写成$maxn$导致模板题$wa$了几百年。真是不应该。

代码：

/*************************************************************************
    > File Name: 5772.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/1 9:47:16
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct edge{int to, cap, rev, flow;};
const int maxx = 10 + 5, maxn = 100 + 5, maxm = maxn * maxn + maxn + 15, INF = 0x3f3f3f3f;
int d[maxm], iter[maxm];
int s, t;
vector<edge>G[maxm * 2];
int a[maxx], b[maxx];
int w[maxn][maxn];
void init()
{
	for(int i = 0; i < maxm; i++) G[i].clear();
}
void addedge(int from, int to, int cap)
{
    G[from].push_back((edge){to, cap, G[to].size(), 0});
    G[to].push_back((edge){from, 0, G[from].size()-1, 0});
}
void bfs()
{
    memset(d, -1, sizeof(d));
    queue<int>q;
    d[s] = 0;
    q.push(s);
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > e.flow && d[e.to] == -1){
                d[e.to] = d[v] + 1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int f)
{
    if(v == t) return f;
    for(int &i = iter[v]; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > e.flow && d[v] == d[e.to] - 1){
            int tf = dfs(e.to, min(f, e.cap - e.flow));
            if(tf > 0){
				e.flow += tf;
                G[e.to][e.rev].flow -= tf;
                return tf;
            }
        }
    }
    return 0;
}
int max_flow()
{
    int flow = 0;
    for(;;){
        bfs();
        if(d[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while((f = dfs(s, INF))>0){
            flow += f;
        }
    }
}
char str[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; ++tt){
		init();
		int n;scanf("%d", &n);
		scanf("%s", str);
		for(int i = 0; i < 10; ++i){
			scanf("%d%d", &a[i], &b[i]);
		}
		int ans = 0;
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				scanf("%d", &w[i][j]);
			}
		}
		s = 0;
		int tot = 10 + n;
		for(int i = 0; i < n; ++i){
			for(int j = i + 1; j < n; j++){
				addedge(s, ++tot, w[i][j] + w[j][i]);
				addedge(tot, i + 1, INF);
				addedge(tot, j + 1, INF);
				ans += w[i][j] + w[j][i];
			}
		}
		t = ++tot;
		for(int i = 1; i <= n; ++i){
			addedge(i, t, a[str[i - 1] - '0']);
			addedge(i, str[i - 1] - '0' + n + 1, INF);
		}
		for(int i = 0; i < 10; ++i){
			addedge(i + n + 1, t, b[i] - a[i]);
		}
		printf("Case #%d: %d\n", tt, ans - max_flow());
	}
	return 0;
}