點擊打開鏈接
題意：動物園有n只貓，m條狗，還有p個小孩，每個小孩有一個喜歡的動物和一個討厭的動物，如果一個小孩喜歡狗，那麼他一定不喜歡貓，每個小孩高興的條件是他喜歡的動物在動物園並且不喜歡的動物不在，問飼養員將那些動物移出動物園可以使最多的小孩高興
思路：最後剩下的小孩他們之間喜歡和討厭的是不會有沖突的，那麼可以轉化為開心的小朋友的最大獨立集，最大獨立集=頂點數-最大匹配；而這個最大匹配是什麼呢，是有矛盾的小朋友的最大匹配，減去後就是沒有矛盾的了
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1010;
struct edge{
int to,cap,rev;
edge(){}
edge(int a,int b,int c){to=a;cap=b;rev=c;}
};
vector G[maxn];
int level[maxn],iter[maxn];
void add_edge(int from,int to,int cap){
G[from].push_back(edge(to,cap,G[to].size()));
G[to].push_back(edge(from,0,G[from].size()-1));
}
void bfs(int s){
memset(level,-1,sizeof(level));
queueque;
level[s]=0;que.push(s);
while(!que.empty()){
int v=que.front();que.pop();
for(unsigned int i=0;i0&&level[e.to]<0){
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f){
if(v==t) return f;
for(int &i=iter[v];i0&&level[v]0){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow=0;
while(1){
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,inf))>0) flow+=f;
}
}
char str1[510][10],str2[510][10];
int main(){
int n,m,p;
while(scanf("%d%d%d",&n,&m,&p)!=-1){
for(int i=0;i
