建设营销型网站的目的,东莞网站建设推广方案,梧州市建设局官方网站,沈阳seo网站推广正题
链接#xff1a; https://www.luogu.org/record/show?rid7921243 大意
就是有n个飞行员#xff0c;m个外籍的#xff0c;然后皇家的和外籍的配对求最大匹配 解题思路
裸网络流二分匹配。 建图#xff1a; 源点S连向左边的点#xff0c;右边点连汇点E#xff…正题
链接 https://www.luogu.org/record/show?rid7921243 大意
就是有n个飞行员m个外籍的然后皇家的和外籍的配对求最大匹配 解题思路
裸网络流二分匹配。 建图 源点S连向左边的点右边点连汇点E然后之间连接所以的边容量都是1 代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;
struct line{int to,next,w;
}a[100010];
int n,m,x,y,d[110],tot,state[110];
int head,tail,ls[110],s,e,ans;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;a[tot].tox;a[tot].nextls[y];a[tot].w0;ls[y]tot;
}
bool bfs()//在残量网上建立分层图
{head0;tail1;memset(d,-1,sizeof(d));d[s]0;state[1]s;do{head;int xstate[head];for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]-1){d[y]d[x]1;state[tail]y;if (ye) return true;//可以到达}}}while (headtail);return false;//不可以到达汇点了
}
int dinic(int x,int flow)
{int rest0,k;if (xe) return flow;for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]d[x]1){rest(kdinic(y,min(a[q].w,flow-rest)));//记录流量a[q].w-k;//减去剩余容量a[q^1].wk;//反向加上流量}}if (!rest) d[x]0;//剪枝return rest;
}
int main()
{scanf(%d%d,n,m);sm1;em2;while (1){scanf(%d%d,x,y);if (x-1 y-1) break;addl(x,y,1);//连接}for (int i1;in;i) addl(s,i,1);for (int in1;im;i) addl(i,e,1);while (bfs()) ansdinic(s,1e9);if (ans0){printf(No Solution!);return 0;}printf(%d\n,ans);for (int i0;itot;i2){if (a[i].to!sa[i^1].to!sa[i].to!ea[i^1].to!e)//判断是在中间用于匹配的边if (a[i^1].w!0)//有流过的printf(%d %d\n,a[i^1].to,a[i].to);//输出}
}
