首页 > 代码库 > cf #254 (Div. 2)
cf #254 (Div. 2)
a题
#include<stdio.h>#include<string.h>char c[101][101];int main(){ long n,m,i,j; scanf("%ld%ld",&n,&m); gets(c[0]); for(i=1;i<=n;i++) gets(c[i]); for(i=1;i<=n;i++) { for(j=0;j<m;j++) if(c[i][j]==‘-‘) printf("-"); else { if((i%2)^(j%2)) printf("W"); else printf("B"); } printf("\n"); } return 0;}
b题 其实就是每个联通快的节点数减1,dfs,并查集都可以。
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>using namespace std;int p[100];int n, m;int find(int x) { int s; for(s = x; p[s] >= 0; s = p[s]); while(s != x) { int tmp = p[x]; p[x] = s; x = tmp; } return s;}int unionSet(int a, int b) { int t1 = find(a); int t2 = find(b); int tmp = p[t1] + p[t2]; if(p[t1] > p[t2]) { p[t1] = t2; p[t2] = tmp; } else { p[t2] = t1; p[t1] = tmp; }}int main() { while(scanf("%d%d", &n, &m) != EOF) { int a, b; for(int i = 0; i <= n; i++) { p[i] = -1; } for(int i = 0; i < m; i++) { scanf("%d%d", &a, &b); int r1 = find(a); int r2 = find(b); if(r1 != r2) { unionSet(a, b); } } int mul = 0; for(int i = 1; i <= n; i++) { if(p[i] < 0) { mul -= (p[i]+1); } } __int64 ans = pow(2.0, mul); printf("%I64d\n", ans); } return 0;}
c题 求最小密度子图,这个在当时学最大密度子图的时候想过,其实就是一条边两个点,因为再添加一条边之后的密度要小于这两部分中最大的那个。
#include <stdio.h>int n,m;double vval[550],eval[500000];int main(){ double ans=0; int i,j,u,v; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%lf",&vval[i]); for(i=1;i<=m;i++) { scanf("%d%d%lf",&u,&v,&eval[i]); if((vval[u]+vval[v])/eval[i]>ans) ans=(vval[u]+vval[v])/eval[i]; } printf("%.9lf\n",ans); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。