1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| #include<iostream> #include<cstdio> #include<queue> #include<cstring> #define maxn 210 using namespace std;
int n, m, K, C[maxn], f[maxn]; int s, t;
struct Edge{ int to, next, w, fi; }e[100000]; int c1, head[maxn]; inline void add_edge(int u, int v, int w, int fi){ e[c1].to = v; e[c1].w = w; e[c1].fi = fi; e[c1].next = head[u]; head[u] = c1++; }
inline void Add_edge(int u, int v, int w, int fi){ add_edge(u, v, w, fi); add_edge(v, u, 0, -fi); }
int la[maxn], pre[maxn], dis[maxn], fl[maxn]; queue<int> Q; bool vis[maxn]; bool spfa(){ memset(vis, 0, sizeof vis); memset(dis, 10, sizeof dis); memset(fl, 10, sizeof fl); Q.push(s); vis[s] = 1; pre[t] = -1; dis[s] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); vis[u] = 0; for(int i = head[u]; ~i; i = e[i].next){ int v = e[i].to, w = e[i].w, fi = e[i].fi; if(w > 0 && dis[v] > dis[u] + fi){ dis[v] = dis[u] + fi; fl[v] = min(fl[u], w); pre[v] = u; la[v] = i; if(vis[v]) continue; vis[v] = 1; Q.push(v); } } } return pre[t] != -1; } int mc, mf; void mcmf(){ while(spfa()){ mf += fl[t]; mc += fl[t] * dis[t]; int now = t; while(now != s){ e[la[now]].w -= fl[t]; e[la[now] ^ 1].w += fl[t]; now = pre[now]; } } cout << mc; }
int main(){ memset(head, -1, sizeof head); scanf("%d%d%d", &n, &m, &K); s = 0; t = n + m + 1; for(int i = 1; i <= m; ++i){ scanf("%d", &C[i]); for(int j = 1; j <= n; ++j) Add_edge(i + n, t, 1, (2 * j - 1) * C[i]); } for(int i = 1; i <= m; ++i) scanf("%d", &f[i]); for(int i = 1; i <= n; ++i){ char c[maxn]; scanf("%s", c + 1); Add_edge(s, i, K, 0); Add_edge(i, t, K - 1, 0); for(int j = 1; j <= m; ++j) if(c[j] == '1') Add_edge(i, j + n, 1, -f[j]); } mcmf(); return 0; }
|