最大流与最小割
POJ 3713: Transferring Sylla
网络流暴力做法：枚举起点终点作为源点和汇点，拆点建图，判断是否可以连续增广三次。
当然这样复杂度约为，肯定会TLE。
有人靠只枚举终点（固定0号点为起点）的方式AC了，但对于如下数据，似乎会出错。
3 6
0 1
0 1
0 1
0 2
0 2
0 2
正解如下：
引理：至少有三条独立路径（除去起点和终点相同）等价于图的点连通度（点连通图为至少删掉多少个点，使得图不连通）大于等于三。
形而上的理解：每删掉一个点，独立路径数就减一，因此两条件等价。
因此，只要枚举删掉一个点，然后判断剩下的图是否是点双联通的即可。（即是否存在割点，不存在，则可行）
具体实现上，求割点用tarjan即可。时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
网络流暴力做法：枚举起点终点作为源点和汇点，拆点建图，判断是否可以连续增广三次。
当然这样复杂度约为O(3n^2*m)，肯定会TLE。
有人靠只枚举终点（固定0号点为起点）的方式AC了，但对于如下数据，似乎会出错。
3 6
0 1
0 1
0 1
0 2
0 2
0 2
正解如下：
引理：至少有三条独立路径（除去起点和终点相同）等价于图的点连通度（点连通图为至少删掉多少个点，使得图不连通）大于等于三。
形而上的理解：每删掉一个点，独立路径数就减一，因此两条件等价。
因此，只要枚举删掉一个点，然后判断剩下的图是否是点双联通的即可。（即是否存在割点，不存在，则可行）
具体实现上，求割点用tarjan即可。时间复杂度O(n*m)。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500+5;
const int maxm=20000+5;
const int INF=0x3f3f3f3f;
int n,m,tot,num,root,dfn[maxn],low[maxn],head[maxn],f[maxm],t[maxm],cut[maxn];
struct node{
int from,to;
}edge[maxm<<1];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void init(int x){
tot=1,num=0;
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(cut,0,sizeof(cut));
if(x==1) root=2;
else root=1;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
int flag=0;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1) cut[x]=1;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Transferring Sylla.in","r",stdin);
while(cin>>n>>m){
if(!n&&!m) break;
for(int i=1;i<=m;i++){
scanf("%d%d",&f[i],&t[i]);
f[i]++,t[i]++;
}
if(n==1){
if(m>=3) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
continue;
}
bool flag;
for(int i=1;i<=n;i++){
init(i);
flag=true;
for(int j=1;j<=m;j++){
if(f[j]==i||t[j]==i) continue;
add(f[j],t[j]),add(t[j],f[j]);
}
tarjan(root);
for(int j=1;j<=n;j++){
if(i==j) continue;
if(!dfn[j]||cut[j]) flag=false;
if(!flag) break;
}
if(!flag) break;
}
if(!flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2987: Firing
最大权闭合子图模板，这里不再赘述。
值得说到的是，最大权闭合子图模型跑完dinic后，从s出发能够访问到的点，都是被选择的点，同时点数满足最少。
因此只要从源点dfs一次，沿着所有没有满流的边能跑到的点集，就是答案集合。
最后，因为少了一个地方没有改成long long，WA了好久。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
最大权闭合子图模板，这里不再赘述。
值得说到的是，最大权闭合子图模型跑完dinic后，从s出发能够访问到的点，都是被选择的点，同时点数满足最少。
因此只要从源点dfs一次，沿着所有没有满流的边能跑到的点集，就是答案集合。
最后，因为少了一个地方没有改成long long，WA了好久。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int maxm=(5000*2+60000)*2+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
struct node{
int from,to;
ll cap;
}edge[maxm];
int n,m,head[maxn],tot=1,d[maxn],s,t,vis[maxn];
ll ans=0,maxflow=0;
void add(int from,int to,ll cap){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].cap=cap;
edge[++tot].from=head[to],head[to]=tot,edge[tot].to=from,edge[tot].cap=0;
}
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
while(q.size()) q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
ll cap=edge[i].cap;
if(cap&&!d[y]){
d[y]=d[x]+1;
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
ll dinic(int x,ll flow){ //注意把int改为longlong的时候，一定要注意函数返回值。
if(x==t) return flow;
ll rest=flow,k;
for(int i=head[x];i&&rest;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap&&d[y]==d[x]+1){
k=dinic(y,min(rest,edge[i].cap));
if(!k) d[y]=0;
edge[i].cap-=k;
edge[i^1].cap+=k;
rest-=k;
}
}
return flow-rest;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap&&!vis[y]){
dfs(y);
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Firing.in","r",stdin);
cin>>n>>m;
s=0,t=n+1;
int from,to;
ll cap;
for(int i=1;i<=n;i++){
cin>>cap;
if(cap>=0){
add(s,i,cap);
ans+=cap;
}
else add(i,t,-cap);
}
for(int i=1;i<=m;i++) cin>>from>>to,add(from,to,INF);
ll flow=0;
while(bfs()){
while(flow=dinic(s,INF)) maxflow+=flow;
}
int cnt=0;
dfs(s);
for(int i=1;i<=n;i++) if(vis[i]) cnt++;
cout<<cnt<<" "<<ans-maxflow;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2914: Minimum Cut
求全局最小割，Stoer-Wagner算法。
题解链接：https://blog.csdn.net/yihuikang/article/details/7730986?locationNum=5
代码如下
/*
求全局最小割，Stoer-Wagner算法。
题解链接：https://blog.csdn.net/yihuikang/article/details/7730986?locationNum=5
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500+5;
const int INF=0x3f3f3f3f;
int n,m,G[maxn][maxn],f[maxn],v[maxn],dis[maxn],min_cut;
void init(){
memset(G,0,sizeof(G));
min_cut=INF;
}
void mincut(){
for(int i=1;i<=n;i++) f[i]=i;
int maxj,pre;
while(n>1){
memset(v,0,sizeof(v));v[f[1]]=1;maxj=2;pre=1; //将1号点所在集合放入最大生成树
for(int i=2;i<=n;i++){
dis[f[i]]=G[f[1]][f[i]];
if(dis[f[i]]>dis[f[maxj]]) maxj=i;
}
for(int i=2;i<=n;i++){
if(i==n){ //生成树处理到最后一条边
min_cut=min(min_cut,dis[f[maxj]]);
// D(maxj);D(dis[f[maxj]]);E;
for(int j=1;j<=n;j++){
G[f[j]][f[pre]]+=G[f[j]][f[maxj]]; //合并进入集合
G[f[pre]][f[j]]=G[f[j]][f[pre]];
}
f[maxj]=f[n--]; //删除maxj 相当于合并
}
v[f[maxj]]=1;pre=maxj;maxj=-1; //将maxj所在集合并入最大生成树
for(int j=2;j<=n;j++){
if(!v[f[j]]){
dis[f[j]]+=G[f[pre]][f[j]];
if(maxj==-1||dis[f[j]]>dis[f[maxj]]) maxj=j;
}
}
}
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Minimum Cut.in","r",stdin);
while(cin>>n>>m){
init();
int from,to,v;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&from,&to,&v);
from++,to++;
G[from][to]+=v;G[to][from]+=v;
}
mincut();
min_cut==INF?cout<<0:cout<<min_cut;
cout<<endl;
}
return 0;
}
POJ 3155: Hard Life
01分数规划+最大密度子图，精度丧心病狂，二分的精度放到1e-8就会WA。
另外double的最大值取0x3f3f3f3f，不要取1e18，否则会WA，原因未知。
建图时，对于mid，化边为点（编号n+1~n+m+1），源点向n+i建边，容量1。
n+i向对应边的两个端点建边，容量INF。
i向汇点建边，容量mid。
最后判断m-最小割是否大于eps即可。
代码如下
/*
01分数规划+最大密度子图，精度丧心病狂，二分的精度放到1e-8就会WA。
另外double的最大值取0x3f3f3f3f，不要取1e18，否则会WA，原因未知。
建图时，对于mid，化边为点（编号n+1~n+m+1），源点向n+i建边，容量1。
n+i向对应边的两个端点建边，容量INF。
i向汇点建边，容量mid。
最后判断m-最小割是否大于eps即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+1000+5;
const int maxm=(1000*3+100)*2+5;
const double eps=1e-6;
const double eps_lim=1e-5;
const int INF=0x3f3f3f3f;
//const double INF=1e18;
struct node{
int from,to;
double cap;
}edge[maxm];
int n,m,head[maxn],tot=1,d[maxn],s,t,vis[maxn],from[maxn],to[maxn],ans=0;
double maxflow;
void init(){
maxflow=m;
memset(head,0,sizeof(head));
tot=1;
}
void add(int from,int to,double cap){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].cap=cap;
edge[++tot].from=head[to],head[to]=tot,edge[tot].to=from,edge[tot].cap=0;
}
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
while(q.size()) q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
double cap=edge[i].cap;
if(cap>eps&&!d[y]){
d[y]=d[x]+1;
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
double dinic(int x,double flow){ //注意把int改为longlong的时候，一定要注意函数返回值。
if(x==t) return flow;
double rest=flow,k;
for(int i=head[x];i&&rest>eps;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap>eps&&d[y]==d[x]+1){
k=dinic(y,min(rest,edge[i].cap));
if(k<eps) d[y]=0;
edge[i].cap-=k;
edge[i^1].cap+=k;
rest-=k;
}
}
return flow-rest;
}
bool check(double mid){
init();
for(int i=1;i<=m;i++){
add(s,n+i,1);add(n+i,from[i],INF);add(n+i,to[i],INF);
}
for(int i=1;i<=n;i++) add(i,t,mid);
while(bfs()){
maxflow-=dinic(s,INF);
}
return maxflow>eps;
}
void dfs(int x){
vis[x]=1;
if(x>=1&&x<=n) ans++;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap>0&&!vis[y]){
dfs(y);
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Hard Life.in","r",stdin);
cin>>n>>m;
if(m==0){
cout<<1<<endl<<1<<endl;
return 0;
}
s=0,t=n+m+1;
for(int i=1;i<=m;i++) cin>>from[i]>>to[i];
double l=0,r=m,ans_lim;
while(r-l>eps_lim){
double mid=(l+r)/2;
if(check(mid)) l=mid,ans_lim=mid;
else r=mid;
}
check(l);dfs(s);
cout<<ans<<endl;
for(int i=1;i<=n;i++) if(vis[i]) cout<<i<<endl;
return 0;
}
二分图匹配
POJ 1274: The Perfect Stall
二分图匹配模板题，不再赘述。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
二分图匹配模板题，不再赘述。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int maxm=200+5;
const int INF=0x3f3f3f3f;
int n,m,match[maxm],vis[maxn],G[maxn][maxm],ans;
bool dfs(int x){
for(int i=1;i<=m;i++){
if(G[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
void init(){
memset(match,0,sizeof(match));
memset(G,0,sizeof(G));
ans=0;
}
int main() {
ios::sync_with_stdio(false);
// freopen("The Perfect Stall.in","r",stdin);
while(cin>>n>>m){
int num,temp;
init();
for(int i=1;i<=n;i++){
cin>>num;
while(num--){
cin>>temp;
G[i][temp]=1;
}
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2112: Optimal Milking
题目要求最大值尽量小，因此二分答案。
首先floyd跑出任意两点最短距离。
对于每个答案mid，在所有距离小于等于mid的、不属于同一集合的点之间建边。另外，源点向奶牛建边，容量为1。机器向汇点建边，容量为M。
接下来用dinic求一下这个二分图的多重匹配是否等于C即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题目要求最大值尽量小，因此二分答案。
首先floyd跑出任意两点最短距离。
对于每个答案mid，在所有距离小于等于mid的、不属于同一集合的点之间建边。另外，源点向奶牛建边，容量为1。机器向汇点建边，容量为M。
接下来用dinic求一下这个二分图的多重匹配是否等于C即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=230+5;
const int maxm=(30*200+30+200)*2+5;
const int INF=0x3f3f3f3f;
struct node{
int from,to,cap;
}edge[maxm];
int K,C,M,head[maxn],tot,d[maxn],s,t,maxflow,dis[maxn][maxn];
void add(int from,int to,int cap){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].cap=cap;
edge[++tot].from=head[to],head[to]=tot,edge[tot].to=from,edge[tot].cap=0;
}
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
while(q.size()) q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,cap=edge[i].cap;
if(cap&&!d[y]){
d[y]=d[x]+1;
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow,k;
for(int i=head[x];i&&rest;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap&&d[y]==d[x]+1){
k=dinic(y,min(rest,edge[i].cap));
if(!k) d[y]=0;
edge[i].cap-=k;
edge[i^1].cap+=k;
rest-=k;
}
}
return flow-rest;
}
void init(){
memset(head,0,sizeof(head));
maxflow=0,tot=1;
}
bool check(int mid){
init();
for(int i=K+1;i<=K+C;i++) add(s,i,1);
for(int i=K+1;i<=K+C;i++) for(int j=1;j<=K;j++) if(dis[i][j]<=mid) add(i,j,INF);
for(int j=1;j<=K;j++) add(j,t,M);
int flow=0;
while(bfs()){
while(flow=dinic(s,INF)) maxflow+=flow;
}
return maxflow==C;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Optimal Milking.in","r",stdin);
cin>>K>>C>>M;
s=0,t=K+C+1;
memset(dis,INF,sizeof(dis));
//源点 0
//汇点 K+C+1
//牛（左侧节点） K+1~K+C
//机器（右侧节点 1~K
for(int i=1;i<=K+C;i++) for(int j=1;j<=K+C;j++){
cin>>dis[i][j];
if(i!=j&&dis[i][j]==0) dis[i][j]=INF;
}
for(int k=1;k<=K+C;k++) for(int i=1;i<=K+C;i++) for(int j=1;j<=K+C;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
/*
for(int i=1;i<=K+C;i++){
for(int j=1;j<=K+C;j++){
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
*/
int l=0,r=INF;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 1486: Sorting Slides
题解链接：//www.greatytc.com/p/4d3f099b0254
POJ 1466: Girls and Boys
由于分男女，所以是二分图，黑白染色后求一下最大独立集即可。
最大独立集=点数-最大匹配。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
由于分男女，所以是二分图，黑白染色后求一下最大独立集即可。
最大独立集=点数-最大匹配。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500+5;
const int INF=0x3f3f3f3f;
int n,match[maxn],vis[maxn],G[maxn][maxn],ans,c[maxn];
bool dfs(int x){
for(int i=1;i<=n;i++){
if(G[x][i]&&!vis[i]&&c[i]==2){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
void init(){
memset(match,0,sizeof(match));
memset(G,0,sizeof(G));
memset(c,0,sizeof(c));
ans=0;
}
void color(int x,int col){
c[x]=col;
for(int i=1;i<=n;i++){
if(!c[i]&&G[x][i]) color(i,3-col);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Girls and Boys.in","r",stdin);
while(cin>>n){
init();
int ignore_num,num,temp;
for(int i=1;i<=n;i++){
scanf("%d: (%d)",&ignore_num,&num);
while(num--){
cin>>temp;
temp++;
G[i][temp]=G[temp][i]=1;
}
}
for(int i=1;i<=n;i++){
if(!c[i]) color(i,1);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(c[i]==1&&dfs(i)) ans++;
}
cout<<n-ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3692: Kindergarten
二分图最大团问题，转化为求补图的最大匹配。答案就是G+B-补图的最大匹配。
原理：
转化为补图，补图中有边的说明是不认识的，那么想要剩下的人都认识，就得把边去掉，也就是去掉最少的点使所有的边都去掉，就是最小路径覆盖。
最小路径覆盖数等于最大二分配匹数。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
二分图最大团问题，转化为求补图的最大匹配。答案就是G+B-补图的最大匹配。
原理：
转化为补图，补图中有边的说明是不认识的，那么想要剩下的人都认识，就得把边去掉，也就是去掉最少的点使所有的边都去掉，就是最小路径覆盖。
最小路径覆盖数等于最大二分配匹数。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int G,B,M,kase=0,match[maxn*2],vis[maxn*2],g[maxn*2][maxn*2],ans;
bool dfs(int x){
for(int i=G+1;i<=G+B;i++){
if(g[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
void init(){
memset(match,0,sizeof(match));
memset(g,0,sizeof(g));
ans=0;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Kindergarten.in","r",stdin);
while(cin>>G>>B>>M){
if(!G&&!B&&!M) break;
cout<<"Case "<<++kase<<": ";
init();
int from,to;
while(M--){
cin>>from>>to;
to+=G;
g[from][to]=g[to][from]=1;
}
for(int i=1;i<=G+B;i++) for(int j=1;j<=G+B;j++) g[i][j]=1-g[i][j];
/*
for(int i=1;i<=G+B;i++){
for(int j=1;j<=G+B;j++){
cout<<g[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1;i<=G;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<G+B-ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2724: Purifying Machine
题意读懂后，剩下的就简单了。
在只有一位不同的字符串之间建边。
注意到每一条边连接的结点一个二进制位有奇数个1，另一个有偶数个1，故为二分图。
答案就是二分图的边覆盖数，即点数-最大匹配。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题意读懂后，剩下的就简单了。
在只有一位不同的字符串之间建边。
注意到每一条边连接的结点一个二进制位有奇数个1，另一个有偶数个1，故为二分图。
答案就是二分图的边覆盖数，即点数-最大匹配。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+5;
const int maxm=(1<<10)+5;
const int INF=0x3f3f3f3f;
int n,m,cnt,match[maxm],vis[maxm],G[maxm][maxm],ans,c[maxm];
string a[maxm],s[maxm];
map<string,int>mp;
void init(){
mp.clear();
memset(match,0,sizeof(match));
memset(G,0,sizeof(G));
memset(c,0,sizeof(c));
cnt=0;
ans=0;
}
void color(int x,int col){
c[x]=col;
for(int i=1;i<=cnt;i++){
if(!c[i]&&G[x][i]) color(i,3-col);
}
}
bool dfs(int x){
for(int i=1;i<=cnt;i++){
if(G[x][i]&&!vis[i]&&c[i]==2){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
bool check(int i,int j){ //判断s[i]和s[j]是否有且只有一位不同
int num=0;
for(int k=0;k<=n-1;k++) if(s[i][k]!=s[j][k]) num++;
return num==1;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Purifying Machine.in","r",stdin);
while(cin>>n>>m){
if(!n&&!m) break;
init();
for(int i=1;i<=m;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int pos=a[i].find("*");
if(pos==string::npos){
if(mp[a[i]]==0){
mp[a[i]]=++cnt;
s[cnt]=a[i];
}
}
else{
a[i][pos]='0';
if(mp[a[i]]==0){
mp[a[i]]=++cnt;
s[cnt]=a[i];
}
a[i][pos]='1';
if(mp[a[i]]==0){
mp[a[i]]=++cnt;
s[cnt]=a[i];
}
}
}
for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt;j++) if(check(i,j)) G[i][j]=G[j][i]=1;
/*
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
cout<<G[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1;i<=cnt;i++){
if(!c[i]) color(i,1);
}
for(int i=1;i<=cnt;i++){
memset(vis,0,sizeof(vis));
if(c[i]==1&&dfs(i)) ans++;
}
cout<<cnt-ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2226: Muddy Fields
比较巧妙的建图，蓝书上有，这里不赘述了。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n,m,G[maxn][maxn],mp[maxn][maxn],mp1[maxn][maxn],vis[maxn],match[maxn],cnt1=0,cnt2=0;
char a[maxn][maxn];
bool dfs(int x){
for(int i=1;i<=cnt2;i++){
if(G[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
void build(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
if(a[i][j-1]=='*') mp[i][j]=mp[i][j-1];
else mp[i][j]=++cnt1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
if(a[i-1][j]=='*') mp1[i][j]=mp1[i-1][j];
else mp1[i][j]=++cnt2;
}
G[mp[i][j]][mp1[i][j]]=1;
}
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("Muddy Fields.in","r",stdin);
while(cin>>n>>m){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cnt1=0,cnt2=0;
memset(mp,0,sizeof(mp));
memset(mp1,0,sizeof(mp1));
memset(match,0,sizeof(match));
memset(G,0,sizeof(G));
build();
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<mp1[i][j];
}
cout<<endl;
}
*/
int ans=0;
for(int i=1;i<=cnt1;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
最小费用流
POJ 3068: "Shortest" pair of paths
拆点建图，最后求流量为2的最小费用流即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
拆点建图，最后求流量为2的最小费用流即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=64*2+5;
const int maxm=10000*2+5;
const int INF=0x3f3f3f3f;
int n,m,head[maxn],d[maxn],v[maxn],incf[maxn],pre[maxn],maxflow,kase=0,ans,tot,s,t;
struct node{
int from,to,cap,cost;
}edge[maxm+maxn];
void add(int from,int to,int cap,int cost){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].cap=cap,edge[tot].cost=cost;
edge[++tot].from=head[to],head[to]=tot,edge[tot].to=from,edge[tot].cap=0,edge[tot].cost=-cost;
}
void init(){
memset(head,0,sizeof(head));
memset(incf,0,sizeof(incf));
memset(pre,0,sizeof(pre));
tot=1;maxflow=2;ans=0;
}
bool spfa(){
queue<int>q;
memset(d,INF,sizeof(d));
memset(v,0,sizeof(v));
d[s]=0,v[s]=1,incf[s]=INF;
q.push(s);
while(q.size()){
int x=q.front();q.pop();v[x]=0;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,cap=edge[i].cap,cost=edge[i].cost;
if(cap){
if(d[y]>d[x]+cost){
d[y]=d[x]+cost;
incf[y]=min(incf[x],cap);
pre[y]=i;
if(!v[y]){
v[y]=1;q.push(y);
}
}
}
}
}
if(d[t]==INF) return false;
return true;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i].cap-=incf[t];
edge[i^1].cap+=incf[t];
x=edge[i^1].to;
}
maxflow-=incf[t];
ans+=d[t]*incf[t];
}
int main() {
ios::sync_with_stdio(false);
//freopen("Shortest pair of paths.in","r",stdin);
while(cin>>n>>m){
if(!n&&!m) break;
init();
s=1,t=2*n;
cout<<"Instance #"<<++kase<<": ";
int from,to,cost;
for(int i=1;i<=m;i++){
cin>>from>>to>>cost;
from++,to++;
add(from+n,to,1,cost);
}
for(int i=2;i<=n-1;i++) add(i,i+n,1,0);
add(s,n+1,2,0);add(n,t,2,0);
while(maxflow>0&&spfa()) update();
if(maxflow>0) cout<<"Not possible"<<endl;
else cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2195: Going Home
题解链接：//www.greatytc.com/p/4d3f099b0254
POJ 3422: Kaka's Matrix Travels
经典的K取方格数，蓝书上有，这里不赘述了。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int maxm=200000+5;
const int INF=0x3f3f3f3f;
struct node{
int from,to,cap,cost;
}edge[maxm];
int n,k,tot=1,s,t,maxflow=0,ans=0,d[maxn],v[maxn],incf[maxn],pre[maxn],head[maxn];
void add(int from,int to,int cap,int cost){
edge[++tot].to=to;
edge[tot].cost=cost;
edge[tot].cap=cap;
edge[tot].from=head[from];
head[from]=tot;
edge[++tot].to=from;
edge[tot].cost=-cost;
edge[tot].cap=0;
edge[tot].from=head[to];
head[to]=tot;
}
int num(int i,int j,int k){ //k==0 表示入点 k==1 表示出点
return (i-1)*n+j+k*n*n;
}
bool spfa(){
queue<int>q;
memset(d,0xcf,sizeof(d));
memset(v,0,sizeof(v));
q.push(s);
d[s]=0;
v[s]=1;
incf[s]=INF; //增广路上各边的最小剩余容量
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=0;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
int cap=edge[i].cap;
int cost=edge[i].cost;
if(cap){
if(d[y]<d[x]+cost){
d[y]=d[x]+cost;
incf[y]=min(incf[x],cap);
pre[y]=i;
if(!v[y]){
q.push(y);
v[y]=1;
}
}
}
}
}
if(d[t]==0xcfcfcfcf) return false;
return true;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i].cap-=incf[t];
edge[i^1].cap+=incf[t];
x=edge[i^1].to; //注意这里是i^1 不是i
}
maxflow+=incf[t];
ans+=d[t]*incf[t];
}
int main() {
ios::sync_with_stdio(false);
//freopen("K取方格数.in","r",stdin);
cin>>n>>k;
s=1,t=2*n*n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int c;
cin>>c;
add(num(i,j,0),num(i,j,1),1,c);
add(num(i,j,0),num(i,j,1),k-1,0);
if(j<n) add(num(i,j,1),num(i,j+1,0),k,0);
if(i<n) add(num(i,j,1),num(i+1,j,0),k,0);
}
}
while(spfa()) update();
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
