汉字域名的网站,网站建设项目描述范文,品牌建设的过程,温州网站制作建设文章目录题目描述解析解析题目描述
在遥远的东方#xff0c;有一个神秘的民族#xff0c;自称Y族。他们世代居住在水面上#xff0c;奉龙王为神。每逢重大庆典#xff0c; Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每…
文章目录题目描述解析解析题目描述
在遥远的东方有一个神秘的民族自称Y族。他们世代居住在水面上奉龙王为神。每逢重大庆典 Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口并且水在河道内按照一个固定的方向流动。显然水系中不会有环流 由于人数众多的原因Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重这些祭祀地点的选择必须非常慎重。准确地说Y族人认为如果水流可以从一个祭祀点流到另外一个祭祀点那么祭祀就会失去它神圣的意义。族长希望在保持祭祀神圣性的基础上选择尽可能多的祭祀的地点。
解析
有一说一本题第二问的方案构造我没有完全理解 首先考虑我们利用类似弗洛伊德的方法求出这个DAG的传递闭包这样问题就转化成了在图中找到最大独立集 考虑把一个点割成入点和出点这样本题就变成了二分图最大独立集直接n-最大匹配即可 然后就是第二问考虑构造出这个最大独立集 考虑一种方法 从右边未匹配的点开始dfs右边走非匹配边左边只走匹配边 只选取左边dfs到的和右边没被dfs到的点 考虑所有情况的边都会被覆盖到所有这样就可以构造出一个最小点覆盖 然后我们取补集就是一个最大独立集
第三问我们只需要强制选该点把这个点和相关点删去然后尝试再跑一边匈牙利看是否只与答案差一即可
解析
#includebits/stdc.h
using namespace std;
const int N305;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}
int n,m,l;
struct node{int from,to,nxt;
}p[N*N*4];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){x,y,fi[x]};fi[x]cnt;
}
int vis[N],mat[N],num,op[N];
bool dfs(int x,int tim){if(vis[x]tim) return false;vis[x]tim;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]x;return true;}}return false;
}
int hungary(){int res0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(mat));for(int i1;in;i){if(dfs(i,i)){res;//printf( ok:%d\n,i);}}return res;
}
bool mp[105][105];
bool jd[N];
void find(int x){if(jd[x]) return;jd[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;jd[to]1;find(mat[to]);}
}
int main(){memset(fi,-1,sizeof(fi));nread();mread();for(int i1;im;i){int xread(),yread();mp[x][y]1;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j) mp[i][j]| (mp[i][k]mp[k][j]);}}for(int i1;in;i){for(int j1;jn;j){if(mp[i][j]) addline(in,j),addline(j,in);}}int reshungary();printf(%d\n,n-res);for(int in1;i2*n;i){mat[mat[i]]i;}for(int in1;i2*n;i){if(!mat[i]) find(i);}for(int i1;in;i){if(!jd[i]jd[in]) printf(1);else printf(0);}printf(\n);for(int i1;in;i){//printf(i%d-----\n,i);memset(fi,-1,sizeof(fi));cnt-1;int tot0;for(int j1;jn;j){if(ji||mp[i][j]||mp[j][i]) op[j]1;else{op[j]0;tot;}}for(int j1;jn;j){for(int k1;kn;k){if(!op[j]!op[k]mp[j][k]){//printf(%d-%d\n,j,k);addline(j,kn);}}}int ohungary();//printf(tot%d res%d\n,tot,o);printf(%d,tot-o1n-res);}return 0;
}
/*
4 4
1 2
3 4
3 2
4 21010
1011
*/
