今天 zkj 大佬来讲课,一晚上有一个这么强的 PPT 太学了! 那么我们步入正题,首先看到图论:
例题 1: lg1144
很简单,我们直接 bfs(因为边权都是 1, 也就是无权图) 求路径数就可以了.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxm=2000010,maxn=1000010,Inf=2147483647;
- const int Mod=100003;
- struct node{
- int to,next;
- }e[maxm*2];
- int front[maxn],cnt;
- int ans[maxn],dis[maxn],vis[maxn];
- void Add(int x,int y){
- e[++cnt].to=y;
- e[cnt].next=front[x];
- front[x]=cnt;
- }
- int main(){
- int i,j,k,n,m;
- scanf("%d%d",&n,&m);
- for(i=1;i<=n;i++)
- dis[i]=Inf;
- for(i=1;i<=m;i++){
- int x,y;
- scanf("%d%d",&x,&y);
- Add(x,y);Add(y,x);
- }
- queue<int >Q;
- while(!Q.empty())Q.pop();
- Q.push(1);
- ans[1]=1;vis[1]=1;
- while(!Q.empty()){
- int u=Q.front();
- Q.pop();
- vis[u]=0;
- for(int i=front[u];i;i=e[i].next){
- int v=e[i].to;
- if(dis[v]>dis[u]+1){
- dis[v]=dis[u]+1;
- ans[v]=ans[u];
- if(!vis[v]){
- vis[v]=1;Q.push(v);
- }
- }
- else if(dis[v]==dis[u]+1)
- ans[v]=(ans[v]+ans[u])%Mod;
- }
- }
- ans[1]=1;
- for(i=1;i<=n;i++)
- printf("%d\n",ans[i]%Mod);
- return 0;
- }
- /*
- Input:
- 5 7
- 1 2
- 1 3
- 2 4
- 3 4
- 2 3
- 4 5
- 4 5
- Output:
- 1
- 1
- 1
- 2
- 4
- */
例题 2:lg1137 原题
- #include<bits/stdc++.h>
- using namespace std;
- const int maxm=200010,maxn=100010;
- struct node{
- int to,next;
- }e[maxm];
- int front[maxn],cnt;
- int vis[maxn],dis[maxn];
- void Add(int u,int v){
- e[++cnt].to=v;
- e[cnt].next=front[u];
- front[u]=cnt;
- }
- int ans[maxn];
- int dfs(int u,int fa){
- if(ans[u])return ans[u];
- ans[u]=1;
- for(int i=front[u];i;i=e[i].next){
- int v=e[i].to;
- if(v==fa)continue;
- dfs(v,u);
- ans[u]=max(ans[u],ans[v]+1);
- }
- return ans[u];
- }
- int main(){
- int i,j,k,n,m;
- scanf("%d%d",&n,&m);
- for(i=1;i<=m;i++){
- int x,y;
- scanf("%d%d",&x,&y);
- Add(y,x);
- }
- for(i=1;i<=n;i++)
- printf("%d\n",dfs(i,i));
- return 0;
- }
- /*
- Input:
- 5 6
- 1 2
- 1 3
- 2 3
- 2 4
- 3 4
- 2 5
- Output:
- 1
- 2
- 3
- 4
- 3
- */
DP:
例题 1:lg1880 石子合并 原题
- #include < stdio.h > #include < stdlib.h > #include < iostream > using namespace std;
- const int Inf = 2147483647,
- maxn = 1010;
- int a[2 * maxn],
- sum[2 * maxn];
- int dp1[maxn * 2][maxn * 2],
- dp2[maxn * 2][maxn * 2];
- int main() {
- int i,
- j,
- k,
- n,
- m;
- scanf("%d", &n);
- for (i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- a[i + n] = a[i];
- }
- for (i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
- for (i = 2 * n - 1; i >= 1; i--) for (j = i + 1; j < i + n; j++) {
- dp1[i][j] = Inf;
- for (k = i; k < j; k++) {
- dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + sum[j] - sum[i - 1]);
- dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
- }
- }
- int ans1 = Inf,
- ans2 = 0;
- for (i = 1; i <= n; i++) {
- ans1 = min(ans1, dp1[i][i + n - 1]);
- ans2 = max(ans2, dp2[i][i + n - 1]);
- }
- printf("%d\n%d\n", ans1, ans2);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2445327.html