兔子的戰役（最小割）

很久很久之前，樹林裡住着一群兔子。但是不幸的時，森林裡還有一匹狼，這匹狼隔三差五就來騷擾兔子，兔子為了抵抗狼的襲擊，也組織了軍隊來與狼戰鬥。這一系列戰役發生在很久之前了，現在的人們隻能通過史書來了解當時的戰役。

我們假設一共有N隻兔子，編号為1-N，史書上記載了K場兔子與狼之間的戰役。每場戰役，兔子們派出這N隻兔子的中的若幹隻（即一個集合）去與狼戰鬥，史書上同時也記錄了這場戰役的結果（兔子勝利或者狼勝利）。但是史書的記錄并不可靠，有時會出現沖突的情況，沖突的情況有以下兩種：

1、有一場戰役兔子集合S去迎戰狼，并且兔子勝利，但是還有一場戰役，兔子集合S’去迎戰狼，但是兔子失敗了。其中S是S’的子集。（這種情況對應了，已經取得勝利的兔子們再加上了一些兔子卻失敗了）

2、有一場戰役兔子集合S去迎戰狼，并且兔子失敗，但是還有一場戰役，兔子集合S’去迎戰狼，但是兔子勝利了。其中S是S’的超集。（這種情況對應了，已經失敗的兔子們再減去了一些兔子卻勝利了）

你需要修改史書上若幹條記錄的結果（即兔子勝利改成失敗，或者失敗改成勝利），使得以上兩種沖突都不會出現。

輸入格式：

第一行兩個整數N和K，分别表示兔子的個數和史書上記錄的個數

接下來K行，每行表示一條記錄。每個記錄由一個整數h開始，表示這場戰役由h個兔子參戰，在接下來h個整數，表示參與這場戰役的兔子們，保證這h個編号互不相同。再最後一個字母W或者F，W表示這場戰役兔子勝利，F表示兔子失敗

輸出格式：

一行一個整數，表示最小修改的記錄條數

資料範圍

N , K ≤ 1000 N,K\le 1000 N,K≤1000

解法

首先根據集合的包含關系連邊，注意如果兩個集合相同，也要連邊。然後我們發現唯一一種沖突情況就是一個大集合輸了，一個小集合反而赢了。如果我們将原圖中一個勝了的集合的權值設為1，一個輸了的集合權值設為0，并且将權值為1的集合與S連邊，權值為0的集合向T連邊，每條邊容量為1，再連結那些有沖突的邊，容量設為inf,那麼答案就是這張圖的最小割。

考慮正确性：一條沒有沖突的邊對答案實際上沒有影響，因為如果這條邊的大集合和某一個集合有沖突，那麼小集合也一定和那個集合有沖突。如果是小集合有沖突，那對于大集合而言沒有影響。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read(){
	char c=getchar();int t=0,f=1;
	while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}
	while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n,k;
struct node{
	int a[1005],h,st;
}a[1005];
struct edge{
	int v,p,w;
}e[2000005];
int h[1005],cnt=1;
vector<int> g[1005];
inline void add(int a,int b,int c){
	e[++cnt].p=h[a];
	e[cnt].v=b;
	e[cnt].w=c;
	h[a]=cnt;
}
int s,t,dis[1005],ht[1005];
bool bfs(){
	queue<int> q;
	while(!q.empty())q.pop();
	q.push(s);
	memset(dis,-1,sizeof(dis));
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].p){
			int v=e[i].v;
			if(e[i].w&&(dis[v]==-1)){
				dis[v]=dis[u]+1;
			//  printf("%d %d\n",v,dis[v]);
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int rest){
	if(u==t||rest==0)return rest;
	int tot=0;
	for(int &i=ht[u];i;i=e[i].p){
		int v=e[i].v;
		if(e[i].w&&(dis[v]==dis[u]+1)){
			int di=dfs(v,min(rest,e[i].w));
			e[i].w-=di;e[i^1].w+=di;
			rest-=di;tot+=di;
			if(rest==0)break;
		}
	}
	return tot;
}
int dinic(){
	int ans=0;
	while(bfs()){
		for(int i=s;i<=t;i++)ht[i]=h[i];
		ans+=dfs(s,inf);
	}
	return ans;
}
signed main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
	n=read(),k=read();
	s=0,t=k+1;
	for(int i=1;i<=k;i++){
		int h=read();
		for(int j=1;j<=h;j++){
			int x=read();
			a[i].a[x]++;
		}
		a[i].h=h;
		char c;
		cin>>c;
		if(c=='W'){
			add(s,i,1);
			add(i,s,0);
			a[i].st=1;
		}
		else {
			add(i,t,1);
			add(t,i,0);
			a[i].st=0;
		}
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			if(a[i].h<a[j].h)continue;
			int flag=1;
			for(int x=1;x<=n;x++){
				if(a[j].a[x]&&(!a[i].a[x])){flag=0;break;}
			}
			if(flag){
				if(a[j].st==1&&a[i].st==0){
				//printf("%d %d\n",i,j);
				add(j,i,inf);
				add(i,j,0);
				}
			}
		}
	}
	printf("%d\n",dinic());
	return 0;
}