「图论」练习
2019-05-09 本文已影响0人
云中翻月
0x6B「图论」练习
POJ3463 Sightseeing
求次短路和方案数统计。需要在dij算法松弛时进行修正。
代码如下
/*
*/
#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>
#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 maxm=10000+5;
const int INF=0x3f3f3f3f;
int T,n,m,head[maxn],tot,S,F,dis[maxn][2],vis[maxn][2],f[maxn][2];
struct point{
int d,x,k;
bool operator<(const point &h)const{return d>h.d;}
};
struct node{
int from,to,c;
}edge[maxm];
priority_queue<point>q;
void add(int from,int to,int c){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].c=c;
}
void dij(){
dis[S][0]=0,f[S][0]=1;
q.push((point){0,S,0});
while(q.size()){
point p=q.top();q.pop();
int d=p.d,x=p.x,k=p.k;
if(vis[x][k]) continue;
vis[x][k]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,c=edge[i].c;
if(d+c<dis[y][0]){
dis[y][1]=dis[y][0],dis[y][0]=d+c;
f[y][1]=f[y][0],f[y][0]=f[x][k];
q.push((point){dis[y][0],y,0});
q.push((point){dis[y][1],y,1});
}
else if(d+c==dis[y][0]) f[y][0]+=f[x][k];
else if(d+c<dis[y][1]){
dis[y][1]=d+c,f[y][1]=f[x][k];
q.push((point){dis[y][1],y,1});
}
else if(d+c==dis[y][1]) f[y][1]+=f[x][k];
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Sightseeing.in","r",stdin);
cin>>T;
while(T--){
memset(dis,INF,sizeof(dis));
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
tot=1;
cin>>n>>m;
int u,v,c;
for(int i=1;i<=m;i++) cin>>u>>v>>c,add(u,v,c);
cin>>S>>F;
dij();
dis[F][0]+1==dis[F][1]?cout<<f[F][0]+f[F][1]<<endl:cout<<f[F][0]<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
6B02 升降梯上
从初始状态spfa跑单源最短路即可。
代码如下
/*
*/
#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>
#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 maxm=20+5;
const int INF=0x3f3f3f3f;
struct node{int x,y;};
queue<node>q;
int n,m,c[maxm],d[maxn][maxm],vis[maxn][maxm],st,ans=INF;
void spfa(){
q.push((node){1,st});d[1][st]=0;vis[1][st]=1;
while(q.size()){
int x=q.front().x,y=q.front().y;q.pop();
vis[x][y]=0;//注意vis数组的操作
for(int i=1;i<=m;i++){
if(x+c[i]>=1&&x+c[i]<=n&&d[x+c[i]][i]>d[x][y]+abs(c[i])*2+abs(y-i)){
d[x+c[i]][i]=d[x][y]+abs(c[i])*2+abs(y-i);
if(!vis[x+c[i]][i]){//注意vis数组的操作
q.push((node){x+c[i],i});
vis[x+c[i]][i]=1;//注意vis数组的操作
}
// D(x);D(y);D(x+c[i]);D(i);D(abs(c[i])*2+abs(y-i));E;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("升降梯上.in","r",stdin);
memset(d,INF,sizeof(d));
cin>>n>>m;
for(int i=1;i<=m;i++){cin>>c[i];if(c[i]==0) st=i;}
spfa();
for(int i=1;i<=m;i++) ans=min(ans,d[n][i]);
ans==INF?cout<<-1:cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
6B03 GF和猫咪的玩具
所谓“拉紧”，就等价于找到两点间的最短路。因此本题所求就是所有两点间最短路中最长的。
代码如下
/*
*/
#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>
#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+5;
const int INF=0x3f3f3f3f;
int n,m,d[maxn][maxn],ans=0;
int main() {
ios::sync_with_stdio(false);
//freopen("GF和猫咪的玩具.in","r",stdin);
cin>>n>>m;
memset(d,INF,sizeof(d));
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
d[u][v]=d[v][u]=1;
}
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(d[i][j]!=INF)ans=max(ans,d[i][j]);
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ2349 Arctic Network
按照两点间距离作为边权建边，求出MST后，输出第s大的边长即可。
代码如下
/*
*/
#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>
#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;
struct node{
int u,v;
double c;
bool operator<(const node &h)const{return c<h.c;}
}edge[maxn*maxn*2];
int T,n,s,f[maxn],tot;
double x[maxn],y[maxn];
vector<double>ans;
double dis(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
void kruskal(){
sort(edge+1,edge+tot+1);
for(int i=1;i<=tot;i++){
int u=find(edge[i].u),v=find(edge[i].v);
if(u==v) continue;
f[u]=v;ans.push_back(edge[i].c);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Arctic Network.in","r",stdin);
cin>>T;
while(T--){
cin>>s>>n;
tot=0;ans.clear();
for(int i=1;i<=n;i++) cin>>x[i]>>y[i],f[i]=i;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) edge[++tot]=(node){i,j,dis(i,j)};
kruskal();
sort(ans.begin(),ans.end());
printf("%.2lf\n",ans[n-s-1]); //这边要有换行 否则会有PE
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
6B06 四叶草魔杖
正解链接 https://www.cnblogs.com/lokiii/p/9342507.html
但我的解法也AC了。暂不知道原因。
说一下我的解法。
由于最后如果存在可行解，会有若干的子图。因此只要跑一次MST，最后判断是否会有权值和不为0的集合即可，若存在，则无解。否则答案就是MST的边权和。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://www.cnblogs.com/lokiii/p/9342507.html
*/
#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>
#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=16+5;
const int INF=0x3f3f3f3f;
int f[maxn],n,m,sz[maxn],ans=0;
struct node{
int u,v,c;
bool operator<(const node &h)const{return c<h.c;}
}edge[maxn*maxn*2];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void kruskal(){
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++){
int u=find(edge[i].u),v=find(edge[i].v);
if(u!=v&&(sz[u]||sz[v])){
f[u]=v,sz[v]+=sz[u],ans+=edge[i].c;
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("四叶草魔杖.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>sz[i],f[i]=i;
for(int i=1;i<=m;i++) cin>>edge[i].u>>edge[i].v>>edge[i].c,edge[i].u++,edge[i].v++;
kruskal();
for(int i=1;i<=n;i++) if(find(i)==i&&sz[i]){
cout<<"Impossible"<<endl;
return 0;
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1275 Cashier Employment
差分约束，具体详见代码。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN=1005;
const int INF=(1<<30)-1;
struct Edge {
int to,nxt,w;
Edge() {
to=nxt=w=-1; //构造函数 仅用于初始化
}
} e[MAXN];
int first[MAXN];
int t,n;
int tot;
int d[MAXN];
int in[MAXN];
int cnt[MAXN];
int R[MAXN];
int num[MAXN];
int inihead[MAXN];
queue<int> q;
void inline Add_Edge(int x,int y,int w) { //链式前向星
tot++;
e[tot].to=y;
e[tot].w=w;
e[tot].nxt=first[x]; //e的下一个是前一个 当第一次进来时 e的上一个不存在 即fisrt的初始值是-1
first[x]=tot;
}
void init() {
int a;
for(int i=1; i<=24; i++)
cin>>R[i]; //1~24点 每个时间需要的人数
cin>>n; //应聘者人数
memset(num,0,sizeof(num));
for(int i=1; i<=n; i++) {
cin>>a;
num[a+1]++; //输入是0~23点 所以这里要+1
}
tot=0;//初始化链式前向星的下标
memset(first,-1,sizeof(first)); //这里的first数组相当于 链式前向星的head数组
memset(e,-1,sizeof(-1));
/*
s[ I ]-s[ I-1 ]>=0 (0<=I<=23)
s[ I-1 ]-s[ I ]>=-num[ I ] (0<=I<=23)
s[ I ]-s[ I-8 ]>=r[ I ] (8<=I<=23)
s[ I ]-s[ I+16 ]>=r[ I ]-s[ 23 ] (0<=I<= 7)
*/
for(int i=1; i<=24; i++) {
if(i>7) Add_Edge(i-8,i,R[i]);
//如果要求最小值的话,变为x-y>=k的标准形式，然后建立一条从y到x的k边，求出最长路径即可
Add_Edge(i,i-1,-num[i]);
Add_Edge(i-1,i,0);
}
for(int i=0; i<25; i++)
inihead[i]=first[i];
//用一个数组暂时存储 因为初始化只有一次 但是二分答案的循环中有加边的操作 这会让first数组改变
}
bool SPFA(int mid) {
for(int i=0; i<=24; i++)
d[i]=-INF,in[i]=0,cnt[i]=0;
q.push(0);
in[0]=1;
cnt[0]++;
d[0]=0;
/*
初始化
原点入队
栈数组 原点为1 其他为0
计数数组 原点为1 其他为0
到原点距离的数组 原点为0 其他为-INF
注意：这里有25个点 0点是虚拟原点 这意味着 其他都需要从1开始存储
————————————————
*/
while(!q.empty()) {
int x=q.front();
q.pop();
in[x]=0; //出栈
for(int i=first[x]; i!=-1; i=e[i].nxt) {
int y=e[i].to;
int w=e[i].w;
if(d[y]<d[x]+w) { //最长路径
d[y]=d[x]+w;
if(!in[y]) { //终点不在栈中
q.push(y);
in[y]=1;
if(++cnt[y]>25) //进入次数超过理论上限（即结点个数） 说明存在负权回路
return false;
}
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
// freopen("小胖超市.in","r",stdin);
cin>>t;
while(t--) {
init();
int l=0,r=n; //二分答案
int ans=INF;
while(l<r) {
int mid=(l+r)/2; //mid即时二分的答案 也是要找的s[24]！
for(int i=0; i<25; i++)
first[i]=inihead[i];//放回来
for(int i=1; i<8; i++) //考虑i<8的情况 因为这个不等式中出现了s[24] 所以要枚举
Add_Edge(i+16,i,R[i]-mid);
Add_Edge(0,24,mid);//从0到24 因为s[0]有意义 s[24]-s[0]>=ans(s[0]=0)
if(SPFA(mid)) {
r=mid; //可以的话 缩小最大值
ans=min(ans,mid);//可以的情况下 才可以ans求min
} else
l=mid+1;
}
if(ans>n) //为了满足条件 需要雇佣的人超过了申请者的数目 无解
cout<<"No Solution"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
6B12 最优高铁环
dfs判断负环即可。注意建图方式。
代码如下
/*
*/
#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>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxm=50005*4+5;
const int INF=0x3f3f3f3f;
const double eps=1e-2;
int m,tot=0,head[maxm],vis[maxm];
double d[maxm],s[maxm],len[maxm],t;
map<string,int>mp;
string s1;
struct node{
int from,to;
}edge[maxm<<1];
void add(int from,int to){
edge[++tot].to=to,edge[tot].from=head[from],head[from]=tot;
}
double cal(char s){
if(s=='S'){
t=0;
return 1000.0;
}
if(s=='G'){
t=1;
return 500.0;
}
if(s=='D'){
t=2;
return 300.0;
}
if(s=='T'){
t=3;
return 200.0;
}
if(s=='K'){
t=4;
return 150.0;
}
return -1;
}
bool dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
double c=len[i];
if(d[y]>d[x]+c){
d[y]=d[x]+c;
if(vis[y]||dfs(y)) return true;
}
}
vis[x]=0;
return false;
}
bool check(double mid){
for(int i=1;i<=m;i++) len[i]=mid-s[i];
memset(vis,0,sizeof(vis));
memset(d,INF,sizeof(d));
for(int i=1;i<=50000;i++) if(dfs(i)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("最优高铁环.in","r",stdin);
cin>>m;
for(int i=1;i<=m;i++){
cin>>s1;
int x=0,st=0,flag=0;
for(int j=0;j<s1.length();j++){
int num=s1[j]-'0';
if(num>=0&&num<=9) x=x*10+num;
else if(s1[j]=='-'){
if(!flag) st=x+int(t)*10000;
flag=1,x=0;
}
else s[i]+=cal(s1[j]);
}
int ed=x+int(t)*10000;
add(st,ed);
}
double L=0.0,R=double(INF),ans=-1;
while(R-L>eps){
double mid=(L+R)/2;
if(check(mid)) L=mid,ans=mid;
else R=mid;
}
printf("%.0lf",ans);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1041 John's trip
题意：求字典序最小的欧拉回路。
首先通过度数，判断是否存在欧拉回路。（所有点度数均为偶数）
然后跑一便euler()即可。注意由于存在字典序，所以要先将边排序。这里使用了链式前向星存图，因为前向星从最后一条边开始扫 所以加边的顺序是降序。
代码如下
/*
*/
#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>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxm=2000+5;
const int maxn=50+5;
const int INF=0x3f3f3f3f;
int n,m,tot,s,head[maxn],deg[maxn],ans[maxm<<1],com[maxm<<1],st[maxm<<1],top,vis[maxm<<1],t;
struct node{
int from,to,z;
}edge[maxm<<1];
struct node1{
int from,to,z;
bool operator<(const node1 &h)const{return z>h.z;}//因为前向星从最后一条边开始扫 所以加边的顺序是降序
}Edge[maxm<<1];
void add(int from,int to,int z){
edge[++tot].to=to,edge[tot].z=z,edge[tot].from=head[from],head[from]=tot;
}
void euler(){
st[++top]=s;
while(top){
int x=st[top],i=head[x];
while(i&&vis[i]) i=edge[i].from;
if(i){
vis[i]=vis[i^1]=1;
st[++top]=edge[i].to;
com[top]=edge[i].z;
head[x]=edge[i].from;
}
else{
ans[++t]=com[top],top--;
}
}
for(int i=t-1;i;i--) cout<<ans[i]<<" ";
cout<<endl;
}
int main() {
ios::sync_with_stdio(false);
//freopen("John's trip.in","r",stdin);
while(1){
n=m=t=top=0,tot=1;
memset(head,0,sizeof(head));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
int x,y,z,f=0;
while(cin>>x>>y&&x&&y){
cin>>z;
Edge[++m]=(node1){x,y,z};
deg[x]++,deg[y]++;
if(!n) s=min(x,y);
n=max(n,max(x,y));
}
if(!n) break;
sort(Edge+1,Edge+m+1);
for(int i=1;i<=m;i++){
add(Edge[i].from,Edge[i].to,Edge[i].z);
add(Edge[i].to,Edge[i].from,Edge[i].z);
}
for(int i=1;i<=n;i++){
if(deg[i]&1){
cout<<"Round trip does not exist."<<endl;
f=1;break;
}
}
if(!f) euler();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
6B18 太鼓达人
答案显然是，考虑使用dfs构造方案。
具体地说，每次优先尝试放置0，再尝试放置1。同时用一个vis数组对最后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>
#include<ctime>
#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=10000+5;
const int INF=0x3f3f3f3f;
int vis[maxn],k,n,t,ans[maxn];
int dfs(int x,int k){
if(vis[x]) return 0;
if(k==t) return 1;
ans[k]=x&1;
vis[x]=1;
if(dfs((x<<1)&(t-1),k+1)) return 1;
if(dfs((x<<1|1)&(t-1),k+1)) return 1;
vis[x]=0;
return 0;
}
int main() {
ios::sync_with_stdio(false);
//freopen("太鼓达人.in","r",stdin);
cin>>n;
t=(1<<n);
cout<<t<<" ";
dfs(0,1);
for(int i=1;i<n;i++) cout<<"0";
for(int i=1;i<=t-n+1;i++) cout<<ans[i];
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
6B24 Place the Robots
若是直接在所有不发生冲突的坐标点之间建边，则转化为图的最大独立集问题，NP不可解。
于是我就去网上找了题解。
考虑图的性质，因为是网格平面，因此将每一行被墙隔开、且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号，如图7.25(a)所示。需要说明的是，最后一行，即第4 行有两个空地，但这两个空地之间没有墙壁，只有草地，所以这两个空地应该属于同一“块”。同样，把竖直方向的块也编上号，如图7.25(b)所示。
图片.png
把每个横向块看作二部图中顶点集合X 中的顶点，竖向块看作集合Y 中的顶点，若两个块有公共的空地（注意，每两个块最多有一个公共空地），则在它们之间连边。例如，横向块2 和竖向块1 有公共的空地，即(2, 0)，于是在X 集合中的顶点2 和Y 集合中的顶点1 之间有一条边。这样，问题转化成一个二部图，如图7.25(c)所示。由于每条边表示一个空地（即一个横向块和一个竖向块的公共空地），有冲突的空地之间必有公共顶点。例如边(x1, y1)表示空地(0, 0)、边(x2, y1)表示空地(2, 0)，在这两个空地上不能同时放置机器人。所以问题转化为在二部图中找没有公共顶点的最大边集，这就是最大匹配问题。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://blog.csdn.net/u014141559/article/details/44409255
*/
#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>
#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=50+5;
const int maxp=51*27+5;
const int INF=0x3f3f3f3f;
int T,n,m,G[maxp][maxp],ans,mp[maxn][maxn],mp1[maxn][maxn],cnt1,cnt2,kase=0,vis[maxp],match[maxp];
char a[maxn][maxn];
void init() {
memset(mp,0,sizeof(mp));
memset(mp1,0,sizeof(mp1));
memset(match,0,sizeof(match));
memset(G,0,sizeof(G));
cnt1=cnt2=ans=0;
}
void build() {
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]!='#'&&mp[i][j]==0) {
cnt1++;
for(int k=j; a[i][k]!='#'&&k<=m; k++) mp[i][k]=cnt1;
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]!='#'&&mp1[i][j]==0) {
cnt2++;
for(int k=i; a[k][j]!='#'&&k<=n; k++) mp1[k][j]=cnt2;
}
}
}
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<mp1[i][j];
}
cout<<endl;
}
*/
for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(a[i][j]=='o')G[mp[i][j]][mp1[i][j]]=1;
/*
for(int i=1; i<=cnt1; i++) {
for(int j=1; j<=cnt2; j++) {
cout<<G[i][j];
}
cout<<endl;
}
*/
}
bool dfs(int x) {
for(int i=1; i<=cnt2; i++) {
if(!vis[i]&&G[x][i]) {
vis[i]=1;
if(!match[i]||dfs(match[i])) {
match[i]=x;
return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Place the Robots.in","r",stdin);
cin>>T;
while(T--) {
cin>>n>>m;
for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)cin>>a[i][j];
init();
build();
for(int i=1; i<=cnt1; i++) {
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<"Case :"<<++kase<<endl;
cout<<ans<<endl;
}
return 0;
}
#endif
POJ2195 Going Home
分析题意可知，本题为二分图最小权完备匹配。使用最小费用最大流可以AC。
具体建图方式：建立虚拟超级源点和汇点。
超级源点向所有m节点建边，容量1，费用0。
所有h节点向超级汇点建边，容量1，费用0。
每个m节点向所有h节点建边，容量1，费用为两个节点的距离。
代码如下（PS：method_1为bfs求两点距离，method_2为直接根据坐标计算）
/*
*/
#define method_1
#ifdef method_1
/*
82ms AC
*/
#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>
#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+10;
const int maxp=300*300+10;
const int INF=0x3f3f3f3f;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int n,m,head[maxp],q[maxp],d[maxp],tot=1,ans,flow,maxflow,s=0,t=maxp-5,vis[maxn][maxn],dis[maxn][maxn],v[maxp],incf[maxp],pre[maxp<<1];
char mp[maxn][maxn];
queue<pii>q1;
struct node{
int from,to,cap,cost;
}edge[maxp<<1];
void add(int from,int to,int cap,int cost){
edge[++tot].to=to,edge[tot].cap=cap,edge[tot].cost=cost,edge[tot].from=head[from],head[from]=tot;
edge[++tot].to=from,edge[tot].cap=0,edge[tot].cost=-cost,edge[tot].from=head[to],head[to]=tot;
}
void init(){
tot=1,maxflow=0,ans=0;
memset(head,0,sizeof(head));
memset(incf,0,sizeof(incf));
}
bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return false;
return true;
}
int cal(int x,int y){
return (x-1)*n+y;
}
void bfs1(int sx,int sy){
memset(vis,0,sizeof(vis));
vis[sx][sy]=1,dis[sx][sy]=0;
while(q1.size()) q1.pop();
q1.push(make_pair(sx,sy));
while(q1.size()){
pii now=q1.front();q1.pop();
int x=now.first,y=now.second;
for(int i=0;i<=3;i++){
int newx=x+dx[i],newy=y+dy[i];
if(check(newx,newy)&&!vis[newx][newy]){
vis[newx][newy]=1,dis[newx][newy]=dis[x][y]+1;
q1.push(make_pair(newx,newy));
if(mp[newx][newy]=='H') add(cal(sx,sy),cal(newx,newy),1,dis[newx][newy]);
}
}
}
}
bool spfa(){
memset(d,INF,sizeof(d));
memset(v,0,sizeof(v));
int l=1,r=1;
q[1]=s,d[s]=0,v[s]=1,incf[s]=INF;
while(l<=r){
int x=q[l];l++;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&&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[++r]=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("Going Home.in","r",stdin);
while(cin>>n>>m){
if(n==0&&m==0) break;
init();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>mp[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(mp[i][j]=='m') bfs1(i,j);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
if(mp[i][j]=='m') add(s,cal(i,j),1,0);
if(mp[i][j]=='H') add(cal(i,j),t,1,0);
}
while(spfa()) update();
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
116ms AC
*/
#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>
#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+10;
const int maxp=300*300+10;
const int INF=0x3f3f3f3f;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int n,m,head[maxp],q[maxp],d[maxp],tot=1,ans,flow,maxflow,s,t,v[maxp],incf[maxp],pre[maxp<<1];
char mp[maxn][maxn];
vector<pii>mx,hx;
queue<pii>q1;
struct node{
int from,to,cap,cost;
}edge[maxp<<1];
void add(int from,int to,int cap,int cost){
edge[++tot].to=to,edge[tot].cap=cap,edge[tot].cost=cost,edge[tot].from=head[from],head[from]=tot;
edge[++tot].to=from,edge[tot].cap=0,edge[tot].cost=-cost,edge[tot].from=head[to],head[to]=tot;
}
void init(){
tot=1,maxflow=0,ans=0;
memset(head,0,sizeof(head));
memset(incf,0,sizeof(incf));
mx.clear();hx.clear();
}
bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return false;
return true;
}
bool spfa(){
memset(d,INF,sizeof(d));
memset(v,0,sizeof(v));
int l=1,r=1;
q[1]=s,d[s]=0,v[s]=1,incf[s]=INF;
while(l<=r){
int x=q[l];l++;v[x]=0; //注意 一定要有 v[x]=0; 因为spfa过程中 有些点会反复入队
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&&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[++r]=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("Going Home.in","r",stdin);
while(cin>>n>>m){
if(n==0&&m==0) break;
init();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='m') mx.push_back(make_pair(i,j));
if(mp[i][j]=='H') hx.push_back(make_pair(i,j));
}
s=0,t=mx.size()+hx.size()+1;
for(int i=0;i<mx.size();i++) add(s,i+1,1,0);
for(int i=0;i<hx.size();i++) add(i+1+mx.size(),t,1,0);
for(int i=0;i<mx.size();i++) for(int j=0;j<hx.size();j++){
int dis=abs(mx[i].first-hx[j].first)+abs(mx[i].second-hx[j].second); //因为路线可以交叉且无阻碍 因此可以不用bfs 直接通过两点坐标求出最短距离
add(i+1,j+1+mx.size(),1,dis);
}
while(spfa()) update();
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
POJ1422 Air Raid
DAG最小路径覆盖，答案等价于点数-拆点二分图的最大匹配。具体地说，就是将原图上的每个点x拆成两个点x和x+n，对于每条边(x,y)，建边(x,y+n)即可。
代码如下
/*
*/
#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>
#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=120*2+5;
const int INF=0x3f3f3f3f;
int T,n,m,tot,head[maxn],ans,vis[maxn],match[maxn];
struct node{
int from,to;
}edge[maxn*4];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void init(){
ans=0,tot=1;
memset(head,0,sizeof(head));
memset(match,0,sizeof(match));
}
bool dfs(int x){
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
if(!vis[y]){
vis[y]=1;
if(!match[y]||dfs(match[y])){
match[y]=x;
return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Air Raid.in","r",stdin);
cin>>T;
while(T--){
init();
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++) cin>>a>>b,add(a,b+n);
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<n-ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1486 Sorting Slide
显然可以将所有数字作为二分图的左部节点，所有窗口作为二分图的右部节点。本题所求就是，判断是否存在唯一的完美匹配方案。
解决方法是，首先进行一边匈牙利算法。然后依次尝试去掉每一条边，去掉后再跑一边匈牙利算法，判断匹配数是否仍旧是n，如果不是，说明这条边的对应关系是确定的。
代码如下
#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>
#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=24*2+5;
const int INF=0x3f3f3f3f;
int kase=0,n,mp[maxn][maxn],match[maxn],vis[maxn],ans,path[maxn];
struct Slide{
int X1,X2,Y1,Y2;
}slide[maxn];
struct Point{
int x,y;
}p[maxn];
void init(){
memset(mp,0,sizeof(mp));
}
bool check(int i,int j){ //判断第i个矩形是否包含第j个点
return (p[j].x>slide[i].X1)&&(p[j].x<slide[i].X2)&&(p[j].y>slide[i].Y1)&&(p[j].y<slide[i].Y2);
}
bool dfs(int x){
for(int i=1;i<=n;i++){
if(!vis[i]&&mp[x][i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
void hungray(){
ans=0;
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Sorting Slide.in","r",stdin);
while(cin>>n){
if(n==0) break;
cout<<"Heap "<<++kase<<endl;
init();
for(int i=1;i<=n;i++) cin>>slide[i].X1>>slide[i].X2>>slide[i].Y1>>slide[i].Y2;
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
if(check(i,j)){
mp[j][i]=1;
}
}
hungray();
for(int i=1;i<=n;i++){
path[i]=match[i];
}
int flag=0;
for(int i=1;i<=n;i++){
mp[path[i]][i]=0; //如果删掉某一条边后变不完美了，说明这条边的对应关系是确定的。
hungray();
if(ans==n) continue;
else{
if(flag) cout<<" "; //去除行尾空格
cout<<"("<<char(i+'A'-1)<<","<<path[i]<<")";
flag=1;
}
mp[path[i]][i]=1;
}
if(!flag){
cout<<"none";
}
cout<<endl<<endl;
}
return 0;
}
POJ1904 King's Quest
二分图完美匹配的可行边和必须边问题，这里有一篇题解讲的很好。
链接 https://blog.csdn.net/a709743744/article/details/52133778
代码如下
/*
https://blog.csdn.net/a709743744/article/details/52133778
*/
#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>
#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=2000*2+5;
const int INF=0x3f3f3f3f;
int n,tot=1,cnt=0,cnt1=0,top=0,head[maxn],inx[maxn],dfn[maxn],low[maxn],st[maxn],c[maxn];
vector<int>scc[maxn],ans[maxn];
struct node{
int from,to;
}edge[maxn*maxn*2];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void tarjan(int x){
low[x]=dfn[x]=++cnt1;
inx[x]=1;st[++top]=x;
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]);
}
else if(inx[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
int y;cnt++;
do{
y=st[top];
top--;
inx[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
}while(x!=y);
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("King's Quest.in","r",stdin);
scanf("%d",&n);
int num,x;
for(int i=1;i<=n;i++){
scanf("%d",&num);
while(num--){
scanf("%d",&x);
add(i,x+n);
}
}
for(int i=1;i<=n;i++){
scanf("%d",&x);
add(x+n,i); //注意不是add(i+n,x);
}
for(int i=1;i<=2*n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=edge[j].from){
int y=edge[j].to;
if(c[i]==c[y]) ans[i].push_back(y-n);
}
sort(ans[i].begin(),ans[i].end());
printf("%d ",ans[i].size());
for(int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1273 Drainage Ditches
最大流模板题，这里使用了dinic算法。
代码如下
/*
*/
#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>
#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 n,m,head[maxn],q[maxn],d[maxn],tot=1,flow,maxflow=0;
struct node{
int from,to,v;
}edge[maxn<<1];
void add(int from,int to,int v){
edge[++tot].to=to,edge[tot].v=v,edge[tot].from=head[from],head[from]=tot;
edge[++tot].to=from,edge[tot].v=0,edge[tot].from=head[to],head[to]=tot;
}
void init(){
tot=1,maxflow=0;
memset(head,0,sizeof(head));
}
bool bfs(){
memset(d,0,sizeof(d));
int l=1,r=1;
q[1]=1,d[1]=1;
while(l<=r){
int x=q[l];
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,v=edge[i].v;
if(v&&!d[y]){
d[y]=d[x]+1;
q[++r]=y;
if(y==m) return 1;
}
}
l++;
}
return 0;
}
int dinic(int x,int flow){
if(x==m) return flow;
int rest=flow,k;
for(int i=head[x];i&&rest;i=edge[i].from){
int y=edge[i].to;
if((d[y]==d[x]+1)&&edge[i].v){
k=dinic(y,min(edge[i].v,rest));
if(!k) d[y]=0;
edge[i].v-=k,edge[i^1].v+=k;
rest-=k;
}
}
return flow-rest;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Drainage Ditches.in","r",stdin);
while(cin>>n>>m){
init();
int a,b,c;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
add(a,b,c);
}
while(bfs())while(flow=dinic(1,INF))maxflow+=flow;
cout<<maxflow<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
