组队赛130829 - from lanshui_Yang

发布时间:2017-6-27 3:02:07 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"组队赛130829 - from lanshui_Yang",主要涉及到组队赛130829 - from lanshui_Yang方面的内容,对于组队赛130829 - from lanshui_Yang感兴趣的同学可以参考一下。

A. Grandpa's Walk        题目大意不再敖述,此题由于数据规模较小,直接用dfs暴力即可,只需注意dfs的起点选取。 代码如下: #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) #define N 1000000007 using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } const int MAXN = 55 ; const int INF = 0xffffffff ; int n , m ; int s[MAXN][MAXN] ; int d[MAXN * MAXN] ; void chu() // 初始化 { int i ; for(i = 0 ; i <= n + 1 ; i ++) s[i][0] = INF ; for(i = 0 ; i <= m + 1; i ++) s[0][i] = INF ; for(i = 0 ; i <= m + 1 ; i ++) s[n + 1][i] = INF ; for(i = 0 ; i <= n + 1 ; i ++) s[i][m + 1] = INF ; } void init() { scanf("%d%d" , &n , &m) ; chu() ; int i , j ; for(i = 1 ; i <= n ; i ++) // 下标均从 1 开始 { for(j = 1 ; j <= m ; j ++) { scanf("%d" , &s[i][j]) ; } } } bool vis[MAXN][MAXN] ; int cango(int x , int y , int p) { if(!vis[x][y] && x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] < p) return 1 ; return 0 ; } int X[4] = {0 , 0 , -1 , 1} ; int Y[4] = {1 , -1 , 0 , 0} ; int MAX ; void dfs(int x , int y) { vis[x][y] = true ; int k ; int pan = 0 ; for(k = 0 ; k < 4 ; k ++) { int tx = x + X[k] ; int ty = y + Y[k] ; if(cango(tx , ty , s[x][y])) { pan = 1 ; vis[tx][ty] = true ; dfs(tx , ty) ; vis[tx][ty] = false ; } } if(pan == 0) MAX ++ ; } void solve() { memset(d , 0 , sizeof(d)) ; int i , j ; MAX = 0 ; for(i = 1 ; i <= n ; i ++) { for(j = 1; j <= m ; j ++) { int k ; int pan = 0 ; for(k = 0 ; k < 4 ; k ++) // 选取起点,只有四周没有比自身大的点才能作为起点 { int tx , ty ; tx = i + X[k] ; ty = j + Y[k] ; if(s[i][j] < s[tx][ty]) { pan = 1 ; break ; } } if(pan == 0) { memset(vis , 0 , sizeof(vis)) ; dfs(i , j) ; } } } printf("%d\n" , MAX) ; } int ca ; int main() { int T ; scanf("%d" , &T) ; ca = 0 ; while (T --) { init() ; printf("Case #%d: " , ++ ca) ; solve() ; } return 0 ; } G. Unique Path       题目大意:给你一个有n个点构成的连通无向图,让你求满足下面条件的点对(a,b)的个数:                                           1、a != b                                           2、从a 到 b 只有一条路径                                           3、满足以上条件的(a , b) 和 (b , a) 算作一个点对。       解题思路:此题样例2的解释中给了我提示,如果一个图是一棵树,那么这棵树中的任意一个点对之间均符合条件,即任意一个点对之间只有一条路径。另外,很自然的想到边连通分量的性质,即在一个边连通分量(这里顶点数 大于1的边连通分量)中,任意一个点对之间至少存在两条不含相同边的可达路径。也就是说在一个边连通分量中的点对不满足上述条件,并且,这个边连通分量中的点与图中不属于该边连通分量的其他点之间也不满足上述条件。所以,此题的解法如下:先用tarjan 找边连通分量,缩点,然后在图中删去顶点个数大于1 的边连通分量及其相关联的边,最后对剩下的图用dfs求解最后答案。 代码如下: #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) #define N 1000000007 using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int ca ; int n , m ; const int MAXN = 10005 ; struct Node { int adj ; int e ; }; int Set[MAXN] ; vector<Node> vert[MAXN] ; bool vis[MAXN] ; bool vise[100005] ; int dfn[MAXN] ; int low[MAXN] ; vector<int> id ; int tmpdfn ; void clr() { int i ; for(i = 0 ; i <= n ; i ++) vert[i].clear() ; for(i = 1 ; i <= n ; i ++) Set[i] = i ; mem(vis , 0) ; mem(vise , 0) ; mem(dfn , -1) ; mem(low , -1) ; id.clear() ; } void init() { RD(n) ; RD(m) ; clr() ; int i , j ; for(i = 1 ; i <= m ; i ++) { int a , b ; RD(a) ; RD(b) ; Node tmp ; tmp.adj = b ; tmp.e = i ; vert[a].push_back(tmp) ; tmp.adj = a ; tmp.e = i ; vert[b].push_back(tmp) ; } } int find(int x) // 并查集 { int r = x ; while (Set[r] != r) { r = Set[r] ; } int t ; while (Set[x] != r) // 并查集优化 { t = Set[x] ; Set[x] = r ; x = t ; } return r ; } int uniset(int x , int y) { int fx = find(x) ; int fy = find(y) ; if(fx < fy) { Set[fy] = fx ; } else Set[fx] = fy ; return min(fx , fy) ; } void tarjan(int u) { vis[u] = true ; dfn[u] = low[u] = ++ tmpdfn ; int i ; int v ; for(i = 0 ; i < vert[u].size() ; i ++) { int v= vert[u][i].adj ; int te = vert[u][i].e ; if(!vise[te]) { vise[te] = true ; if(!vis[v]) { tarjan(v) ; low[u] = min(low[u] , low[v]) ; if(low[v] <= dfn[u]) { int tmp = uniset(u , v) ; id.push_back(tmp) ; } } else low[u] = min(low[u] , dfn[v]) ; } } } int su ; void dfs(int u) { su ++ ; vis[u] = true ; int i ; for(i = 0 ; i < vert[u].size() ; i ++) { int v = vert[u][i].adj ; if(!vis[find(v)]) { dfs(find(v)) ; } } } void solve() { tmpdfn = 0 ; int i ; for(i = 1 ; i <= n ; i ++) { if(!vis[i]) { tarjan(i) ; } } mem(vis , 0) ; for(i = 0 ; i < id.size() ; i ++) { int v = id[i] ; vis[v] = true ; } int ans = 0 ; for(i = 1 ; i <= n ; i ++) { int u = find(i) ; if(!vis[u]) { su = 0 ; dfs(u) ; int tmp = su ; ans += tmp * (tmp - 1) / 2 ; } } OT(ans) ; puts("") ; } int main() { int T ; RD(T) ; while (T --) { init() ; printf("Case #%d: " , ++ ca) ; solve() ; } return 0 ; }

上一篇:这篇文章为什么能发表在Science上?
下一篇:java第十四次课后笔记

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。