1. 题目

传送门=￣ω￣=

2. 题解

这个题是一个很经典的问题：最大点权问题

二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。

独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。

结论: 最大点权独立集 = 所有点权 – 最小点权覆盖集 = 所有点权 – 最小割集 = 所有点权 – 网络最大流。

（以上摘自 http://blog.csdn.net/kevin66654/article/details/52540081）

相关论文：https://wenku.baidu.com/view/986baf00b52acfc789ebc9a9.html

论文末尾有对这个问题的具体解释。

具体做法：
首先黑白染色，黑色四周四个格子是白色，白色四周四个格子是黑色。

接着从源点各连一条边到每个黑色格子上，容量为该黑色格子中的数字。

然后所有的白点各连一条边到汇点，容量为该白色格子中的数字。

最后，从每个黑色格子向与它相邻的四个白色格子（边缘上的格子没有四个）连一条容量无限大的边。

跑最大流得到最大流量为 maxflow。

然后拿所有格子中的数字之和减去这个 maxflow 就是答案了。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct edge{int u,v,c;}e[100000];
int k,n,cnt,T,from[2000];
vector<int> g[2000];
bool book[2000];
queue<int> que;
void adde(int a,int b,int c)
{
    g[a].push_back(cnt),e[cnt++]=(edge){a,b,c};
    g[b].push_back(cnt),e[cnt++]=(edge){b,a,0};
}
bool bfs()
{
    while(!que.empty())que.pop();
    memset(book,0,sizeof(book)),que.push(0),book[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(int i=0;i<g[F].size();i++)if(!book[e[g[F][i]].v]&&e[g[F][i]].c)
            from[e[g[F][i]].v]=g[F][i],que.push(e[g[F][i]].v),book[e[g[F][i]].v]=1;
        if(book[T])return 1;
    }
    return 0;
}
void mxf()
{
    int MX=INT_MAX;
    for(int i=from[T];i!=-1;i=from[e[i].u])MX=min(MX,e[i].c);
    for(int i=from[T];i!=-1;i=from[e[i].u])e[i].c-=MX,e[i^1].c+=MX;
}
int main()
{
    IN(k),IN(n),T=k+n+1,from[0]=-1;
    for(int i=1,j;i<=k;i++)IN(j),adde(0,i,j);
    for(int i=1,j,tmp;i<=n;i++)
    {
        IN(j);
        for(int l=1;l<=j;l++)IN(tmp),adde(tmp,k+i,1);
        adde(k+i,T,1);
    }
    while(bfs())mxf();
    for(int i=1;i<=k;i++)if(book[i])puts("No Solution!"),exit(0);
    for(int i=1;i<=k;i++,putchar('\n'))
    {
        printf("%d:",i);
        for(int j=0;j<g[i].size();j++)
            if(!e[g[i][j]].c&&e[g[i][j]].v)printf(" %d",e[g[i][j]].v-k);
    }
    return 0;
}