Codeforces GYM 101147E. Jumping
传送门：http://codeforces.com/gym/101147/problem/E 题目翻译 求点N到每个点的最短路 题解 建边SPFA直接跑 代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
//while(true) RP++; #include<cstdio> #include<queue> #include<cstring> using namespace std; const int Maxn=1e5; int n; int dist[Maxn+5]; bool inque[Maxn+5]; queue<int> que; struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; Edge e[Maxn*2+5]; int nume; int head[Maxn+5]; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]); head[u]=nume; } inline void spfa(int src){ memset(dist,-1,sizeof(dist)); memset(inque,false,sizeof(inque)); while(!que.empty()) que.pop(); dist[src]=0; inque[src]=true; que.push(src); while(!que.empty()){ int now=que.front(); que.pop(); for (int i=head[now];i;i=e[i].nxt){ if (dist[e[i].v]==-1 || dist[e[i].v]>dist[now]+1){ dist[e[i].v]=dist[now]+1; if (!inque[e[i].v]){ inque[e[i].v]=true; que.push(e[i].v); } } } inque[now]=false; } } inline void solve(int T){ memset(head,0,sizeof(head)); nume=0; scanf("%d",&n); for (int i=1;i<=n;i++){ int jump; scanf("%d",&jump); if (i-jump>=1) addEdge(i-jump,i); if (i+jump<=n) addEdge(i+jump,i); } spfa(n); for (int i=1;i<=n;i++) printf("%d\n",dist[i]); } int main(){ freopen("jumping.in","r",stdin); int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
HDU 5961 传递
传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=5961 题解 满足题意，那么从每个点出发BFS，如果联通那么最短路长度<=1 每个点跑一下SPFA，判断一下就可以了。 代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<queue> using namespace std; const int Maxn=2016; struct Edge{ int v,nxt; Edge(int v0,int n0){ v=v0; nxt=n0; } Edge(){}; }; int head[Maxn+5]; Edge e[Maxn*Maxn+5]; int nume; inline void initEdge(){ nume=0; memset(head,0,sizeof(head)); } inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]); head[u]=nume; //e[++nume]=Edge(u,head[v]); //head[v]=nume; } int n; int ttMap[Maxn+5][Maxn+5]; inline int read(){ char ch=getchar(); while(!(ch=='P' || ch=='Q' || ch=='-')) ch=getchar(); if (ch=='P') return 1; if (ch=='Q') return -1; return 0; } queue<int> que; bool inque[Maxn+5]; int dist[Maxn+5]; inline bool bfs(int src){ while(!que.empty()) que.pop(); memset(inque,false,sizeof(inque)); memset(dist,-1,sizeof(dist)); inque[src]=true; dist[src]=0; que.push(src); while(!que.empty()){ int now=que.front(); que.pop(); for (int i=head[now];i;i=e[i].nxt){ int v=e[i].v; if (dist[v]==-1 || dist[v]>dist[now]+1){ dist[v]=dist[now]+1; if (dist[v]>=2) return false; if (!inque[v]){ inque[v]=true; que.push(v); } } } inque[now]=false; } /*printf("#%d:",src); for (int i=1;i<=n;i++) printf(" %d ",dist[i]); printf("\n");*/ return true; } inline bool judge(int now){ initEdge(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (ttMap[i][j]==now) addEdge(i,j); for (int i=1;i<=n;i++) if (!bfs(i)) return false; return true; } inline void solve(int T){ scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ttMap[i][j]=read(); /*for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ printf("%d ",ttMap[i][j]); } printf("\n"); }*/ if (judge(1)&&judge(-1)) printf("T\n"); else printf("N\n"); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
刷刷POI，整个人都POI！
BZOJ 1098: [POI2007]办公楼biu 补图联通块直接DFS出来就行了，很容易TLE要用链表及时删点、
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; const int Maxm=2000010; inline int read(){ int x = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x; } struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; int head[Maxn]; Edge e[Maxm*2]; int nume; int n,m; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]);head[u]=nume; e[++nume]=Edge(u,head[v]);head[v]=nume; } int nxt[Maxn],pre[Maxn]; inline void del(int x){ int tmp=pre[x]; nxt[tmp]=nxt[x]; pre[nxt[x]]=tmp; } bool vis[Maxn]; int cnt; int siz[Maxn]; bool noEdge[Maxn]; int que[Maxn]; int l,r; int i; void bfs(int src){ que[0]=src; vis[src]=true; for (l = r = 0; l <= r; ++l){ int x=que[l]; //printf("%d\n",x); siz[cnt]++; for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true; for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i] && !noEdge[i]){ del(i); vis[i]=true; que[++r]=i; } } for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false; } } inline void input(){ freopen("1098.in","r",stdin); //freopen("1098.out","w",stdout); } int main(){ //input(); n=read();m=read(); int x,y; for (i=1;i<=m;i++){ x=read(),y=read(); addEdge(x,y); } for (i=0;i<=n;i++){ nxt[i]=i+1; pre[i+1]=i; } for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i]){ cnt++; del(i); bfs(i); } } sort(siz+1,siz+cnt+1); printf("%d\n",cnt); for (i=1;i<=cnt;i++){ printf("%d ",siz[i]); } printf("\n"); return 0; } |
BZOJ 1097: [POI2007]旅游景点atr 首先SPFA出前k+1个点的最短路,然后做状压DP. pre […]
