解法:最大權(quán)閉合圖,網(wǎng)絡(luò)流解,也比較裸。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 205
#define INF 1 << 29
bool mark[N];
int g[N][N];
int ISAP(int src, int sink, int n)
{
int maxflow = 0, flow, u = src, v, d;
int cnt[N], dis[N], pre[N];
memset(cnt, 0, sizeof(cnt));
memset(dis, 0, sizeof(dis));
cnt[0] = n;
pre[src] = src;
while(dis[src] < n)
{
if(u == sink)
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
{
if(g[pre[i]][i] < flow)
flow = g[pre[i]][i];
}
maxflow += flow;
u = src;
for(int i = sink; i != src; i = pre[i])
{
g[pre[i]][i] -= flow;
g[i][pre[i]] += flow;
}
}
for(d = n, v = 0; v < n; v++)
{
if(!g[u][v]) continue;
d = d < dis[v] ? d : dis[v];
if(dis[v] + 1 == dis[u]) break;
}
if(v < n) pre[v] = u, u = v;
else
{
if(!(--cnt[dis[u]])) break;
++cnt[dis[u] = d + 1];
if(u != src) u = pre[u];
}
}
return maxflow;
}
void dfs(int u, int n)
{
mark[u] = 1;
for(int i = 0; i < n; i++)
if(!mark[i] && g[i][u])
dfs(i, n);
}
int main()
{
int t, n, m, src, sink, ans1, ans2[N], top;
int key, treasure;
scanf("%d", &t);
while(t--)
{
memset(g, 0, sizeof(g));
memset(ans2, 0, sizeof(ans2));
memset(mark, 0, sizeof(mark));
scanf("%d %d", &n, &m);
src = ans1 = top = 0, sink = n + m + 1;
for(int i = 1; i <= n; i++)
{
scanf("%d", &key);
g[i + m][sink] = key;
}
for(int i = 1; i <= m; i++)
{
scanf("%d", &treasure);
g[src][i] = treasure;
ans1 += treasure;
}
for(int i = 1; i <= m; i++)
{
int num, id;
scanf("%d", &num);
for(int j = 0; j < num; j++)
{
scanf("%d", &id);
g[i][id + m] = INF;
}
}
ans1 -= ISAP(src, sink, sink + 1);
printf("%d\n", ans1);
dfs(sink, sink);
for(int i = m + 1; i < sink; i++)
{
if(!mark[i])
{
ans2[top++] = i - m;
}
}
printf("%d", top);
for(int i = 0; i < top; i++)
{
printf(" %d", ans2[i]);
}
printf("\n");
}
return 0;
}