善意的投票(最大流最小割，建图技巧）

题意：有m对好朋友关系每个人有不同的想法，每个人可以改变自己的想法，如果改变的话会让答案值+1 问好朋友之间冲突的个数最小值。
思路：
把不同的想法的点，分别与S和T连边，如果两个人之间是好朋友就代表可能会有冲突，那么就连双向边。

#include<bits/stdc++.h>
using namespace std;
const int N=5510,M=N*100*2;
int h[N],ne[M],e[M],idx,d[N],cur[N],q[N],f[M];
void add(int a,int b,int c)
{
   
	e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}
int n,m,S,T;
const int INF=1e9;
char g[N][N];
int get(int x,int y)
{
   
	return (x-1)*m+y;
}
bool bfs()
{
   
	int hh=0,tt=0;
	q[0]=S;
	memset(d,-1,sizeof d);
	d[S]=0;
	cur[S]=h[S];
	while(hh<=tt)
	{
   
		int t=q[hh++];
		for(int i=h[t];~i;i=ne[i])
		{
   
			int j=e[i];
			if(d[j]==-1&& f[i])
			{
   
				cur[j]=h[j];
				d[j]=d[t]+1;
				if(j==T)
				return true;
				q[++tt]=j;			
			}
		}	
	}
	return false;
}
int dfs(int u,int lim)
{
   
	if(u==T)
	return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim ;i=ne[i])
	{
   
		int j=e[i];
		if(d[j]==d[u]+1 && f[i])
		{
   
			int t=dfs(j,min(lim-flow,f[i]));
			if(!t)
			d[j]=-1;
			flow+=t,f[i]-=t,f[i^1]+=t;
		}
	}
	return flow;
}
int dinic()
{
   
	int r=0,flow;
	while(bfs())
	while(flow=dfs(S,INF))
	r+=flow;
	return r;
}
int main()
{
   
	int t;
	//cin>>t;
	t=1;
	while(t--)
	{
   
		idx=0;
		int a,b;
		memset(h,-1,sizeof h);
		S=0,T=N-1;
		cin>>n>>m;//>>a>>b;
		for(int i=1;i<=n;i++)
		{
   
			int x;
			cin>>x;
			if(x==1)
			add(S,i,1);
			else
			add(i,T,1);
		}
		while(m--)
		{
   
			int a,b;
			cin>>a>>b;
			add(a,b,1);
			add(b,a,1);
		}
	cout<<dinic()<<endl;
	}
	return 0;
}

本题变种：
题意：走完图中n+m条直线的最小花费，一开始以为是最小费用流，结果很难对应到要走的直线上去。。。。就很难受，后来问了lcdl，原来是最小割，我大意了啊，不会写，其实这题抽象完就是上面一道题，相邻两点之间代表可能会有冲突，改变高山平地代表改变想法，如果源点与某点存在割边，那么就代表了改变想法，如果两点之间存在割边，代表直接走，hhhh，我是废物。那么对于任意一个s和t不连通的图，我们都能构造出来一组解 tql。

#include<bits/stdc++.h>
using namespace std;
const int N=5510,M=N*100*2;
int h[N],ne[M],e[M],idx,d[N],cur[N],q[N],f[M];
void add(int a,int b,int c)
{
   
	e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}
int n,m,S,T;
const int INF=1e9;
char g[N][N];
int get(int x,int y)
{
   
	return (x-1)*m+y;
}
bool bfs()
{
   
	int hh=0,tt=0;
	q[0]=S;
	memset(d,-1,sizeof d);
	d[S]=0;
	cur[S]=h[S];
	while(hh<=tt)
	{
   
		int t=q[hh++];
		for(int i=h[t];~i;i=ne[i])
		{
   
			int j=e[i];
			if(d[j]==-1&& f[i])
			{
   
				cur[j]=h[j];
				d[j]=d[t]+1;
				if(j==T)
				return true;
				q[++tt]=j;			
			}
		}	
	}
	return false;
}
int dfs(int u,int lim)
{
   
	if(u==T)
	return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim ;i=ne[i])
	{
   
		int j=e[i];
		if(d[j]==d[u]+1 && f[i])
		{
   
			int t=dfs(j,min(lim-flow,f[i]));
			if(!t)
			d[j]=-1;
			flow+=t,f[i]-=t,f[i^1]+=t;
		}
	}
	return flow;
}
int dinic()
{
   
	int r=0,flow;
	while(bfs())
	while(flow=dfs(S,INF))
	r+=flow;
	return r;
}
int main()
{
   
	int t;
	cin>>t;
	while(t--)
	{
   
		idx=0;
		int a,b;
		memset(h,-1,sizeof h);
		cin>>n>>m>>a>>b;
		for(int i=1;i<=n;i++)
		scanf("%s",g[i]+1);
		S=0,T=N-1;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
   
			if(i!=n)
			add(get(i,j),get(i+1,j),a),add(get(i+1,j),get(i,j),a);
			if(j!=m)
			add(get(i,j),get(i,j+1),a),add(get(i,j+1),get(i,j),a);
			if(g[i][j]=='.')
			add(S,get(i,j),b);
			else
			add(get(i,j),T,b);
		}
	cout<<dinic()<<endl;
	}
	return 0;
}