## Solución al problema número 10779 de UVA - 10779.

Cualquier duda no dudes en contactar.

``````#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000 + 7;
const int inf = 0x3f3f3f3f;

struct Edge{
int from, to, cap, flow;
};

struct Dinic{
int n, m, s, t;
vector<Edge>edges;
vector<int>G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];

void init(int nn){
edges.clear();
for (int i = 0; i < nn; ++i)G[i].clear();
}

edges.push_back((Edge){from,to,cap,0});
edges.push_back((Edge){to,from,0,0});
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}

bool BFS(){
memset(vis,0,sizeof vis);
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for (unsigned int i = 0; i < G[x].size(); ++i){
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}

int DFS(int x,int a){
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); ++i){
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0){
e.flow += f;
edges[G[x][i]^1 ].flow -= f;
flow += f;
a -= f;
if (!a)break;

}

}
return flow;
}

int maxflow(int s,int t){
this->s = s; this->t = t;
int flow = 0;
while(BFS()){
memset(cur,0,sizeof cur);
flow += DFS(s,inf);
}
return flow;
}

}dic;

int main() {

int  n,m,x,ca=1, k,cases;
scanf("%d",&cases);
while(cases--) {
scanf("%d %d", &n, &m);
dic.init(n+m+1);
int S,T; S=1; T=n+m+1;
int cromos[100][100];
memset(cromos,0,sizeof(cromos));
for(int i = 1; i <=n; i++)
{
scanf("%d",&k);
for(int j = 0; j <k; j++) {
scanf("%d",&x);
cromos[i][x]++;
}
}
for(int i=1; i<=m;i++)
{
}
for(int i=2; i<=n;i++)
{
for(int j=1; j<=m;j++)
{