电商网站开发ppt,开发一套程序多少钱,重庆做木门网站公司,视频直播源码正题 题目大意
有KKK个点#xff0c;NNN个点a∈Aa\in Aa∈A#xff0c;MMM个点b∈Bb\in Bb∈B。 给x∈Bx\in Bx∈B点集匹配一个y∈Ay\in Ay∈A点集的点#xff0c;使他之间的最长最短路径最短。 解题思路 FlodyFlodyFlody暴力预处理最短路#xff0c;然后二分答案midmidmi…正题 题目大意
有KKK个点NNN个点a∈Aa\in Aa∈AMMM个点b∈Bb\in Bb∈B。 给x∈Bx\in Bx∈B点集匹配一个y∈Ay\in Ay∈A点集的点使他之间的最长最短路径最短。 解题思路
FlodyFlodyFlody暴力预处理最短路然后二分答案midmidmid。
将最短路长度小与midmidmid的a∈Aa\in Aa∈A和b∈Bb\in Bb∈B之间连边然后最大匹配。若匹配数为MMM那么就可行的。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define N 110
using namespace std;
struct line{int x,y,next;
}a[N*N];
int link[N],n,m,ls[N],s,tot,f[N][N],p1[N],p2[N],p;
bool cover[N];
void addl(int x,int y){a[tot].xx;a[tot].yy;a[tot].nextls[x];ls[x]tot;
}
bool find(int x)//最大匹配
{int p0;for (int qls[x];q;qa[q].next){if (!cover[a[q].y]){plink[a[q].y];link[a[q].y]x;cover[a[q].y]true;if (!p || find(p)) return true;link[a[q].y]p;}}return false;
}
int check(int x){//check二分的答案s0;memset(ls,0,sizeof(ls));tot0;memset(link,0,sizeof(link));for(int i1;in;i)for(int j1;jm;j)if(f[p1[i]][p2[j]]x) addl(i,j);//连边for(int i1;in;i){memset(cover,0,sizeof(cover));if(find(i)) s;}//匹配return sm;
}
int main()
{freopen(c.in,r,stdin);freopen(c.out,w,stdout);scanf(%d,p);for(int i1;ip;i)for(int j1;jp;j)scanf(%d,f[i][j]);for(int i1;ip;i)//Flodyfor(int j1;jp;j)for(int k1;kp;k)f[i][j]min(f[i][k]f[k][j],f[i][j]);scanf(%d,n);for(int i1;in;i)scanf(%d,p1[i]);scanf(%d,m);for(int i1;im;i)scanf(%d,p2[i]);int l1,r1e6;while(lr){//二分答案int mid(lr)/2;if(check(mid)) rmid-1;else lmid1;}printf(%d,l);
}
