「codeforces」图论杂题
一些图论简单题：
500A.New Year Transportation
437C.The Child and Toy
510C.Fox And Names
475B.Strongly Connected City
639B.Bear and Forgotten Tree 3
623A.Graph and String
449B.Jzzhu and Cities
543B.Destroying Roads
500A.New Year Transportation
有n个城市排成1排，从第i个城市可以走到\(i+a_i\)号城市，并给定一个城市t，问是否能从1到t？
\(1\leq n,a_i\leq 10^5\)
题解
将1打个标记，从左往右扫一遍，若i打上标记，则将\(i+a_i\)打标记
最后看t是否有标记。
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-6 #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll 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; } int n,t; int a[30005]; bool mark[30005]; int main() { n=read();t=read(); for(int i=1;i<n;i++)a[i]=read(); mark[1]=1; for(int i=1;i<n;i++) if(!mark[i])continue; else mark[i+a[i]]=1; if(mark[t])puts("YES"); else puts("NO"); return 0; } |
437C.The Child and Toy
n个带权点，m条边的无向图，删除一个点的代价是与这个点相邻的，且没有被删除的点权和。
求将所有点删除的最小代价。
题解
按照从大到小的次序删点。
发现每条边的贡献是连接的两个点的权值的最小值。
\(1\leq n\leq1000,1\leq m\leq 2000\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,w[1005]; long long ans=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++) { int x,y; scanf("%d %d",&x,&y); ans+=min(w[x],w[y]); } printf("%lld",ans); return 0; } |
510C.Fox And Names
给定n个字符串，问能否存在这样的字母表，使得字符串的排序满足字典序。
\(1\leq n,|S|\leq 100\)
题解
建图后拓扑排序
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,top,tot,d[105],st[105]; char a[105][105],b[105]; vector<int>e[105]; void insert(int u,int v) { e[u].push_back(v); d[v]++; } bool topsort() { while(top) { int now=st[top--];b[++tot]=now+'a'-1; for(int i=0;i<e[now].size();i++) { int v=e[now][i]; d[v]--;if(!d[v])st[++top]=v; } } for(int i=1;i<=26;i++)if(d[i])return 0; return 1; } int main() { n=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int t1=strlen(a[i]+1),t2=strlen(a[j]+1); for(int k=1;k<=t1;k++) if(k>t2){puts("Impossible");return 0;} else if(a[i][k]!=a[j][k]) { insert(a[i][k]-'a'+1,a[j][k]-'a'+1);break; } } for(int i=1;i<=26;i++)if(!d[i])st[++top]=i; if(!topsort())puts("Impossible"); else { for(int i=1;i<=tot;i++)printf("%c",b[i]); } return 0; } |
475B.Strongly Connected City
给定n条水平和m条竖直的单向街道，其互相交叉为n*m个结点，问这些结点是否都能互相到达。
\(1\leq n,m\leq 20\)
题解
1.从每个结点开始dfs，最后看每个结点是否最终被搜到n*m次。
2.求强连通图可以直接套用tarjan算法。
3.实际上只需要判断外环路是否成环即可。
|
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 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char ch[55]; int n,m,cnt; int id[55][55]; bool vis[2505]; struct edge{int to,next;}e[1000005];int last[2505]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void dfs(int x) { vis[x]=1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) dfs(e[i].to); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=(i-1)*m+j; scanf("%s",ch+1); for(int i=1;i<=n;i++) if(ch[i]=='>') for(int x=1;x<m;x++)insert(id[i][x],id[i][x+1]); else for(int x=2;x<=m;x++)insert(id[i][x],id[i][x-1]); scanf("%s",ch+1); for(int i=1;i<=m;i++) if(ch[i]=='v') for(int x=1;x<n;x++)insert(id[x][i],id[x+1][i]); else for(int x=2;x<=n;x++)insert(id[x][i],id[x-1][i]); for(int i=1;i<=n*m;i++) { dfs(i); for(int x=1;x<=n*m;x++) if(vis[x]!=1){puts("NO");return 0;} else vis[x]=0; } puts("YES"); return 0; } |
639B.Bear and Forgotten Tree 3
构造一棵n个点，深度h，最长链为d的树。
\(1\leq n,h,d\leq 10^5\)
题解
首先构造一个长度为d的链，然后把其中一个距离边上为h的点变为根。
把剩下的点全都接在根上。
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define eps 1e-13 #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,h,d; int fa[1000005]; int main() { n=read();d=read();h=read(); for(int i=2;i<=h+1;i++)fa[i]=i-1; for(int i=1;i<=d-h;i++) if(i==1)fa[i+h+1]=1; else fa[i+h+1]=i+h; if(d==1&&n!=2) { puts("-1"); return 0; } if(d>2*h||d<h||d+1>n) { puts("-1"); return 0; } for(int i=d+2;i<=n;i++)fa[i]=h; for(int i=2;i<=n;i++) printf("%d %d\n",i,fa[i]); return 0; } |
623A.Graph and String
n个结点的无向图，每个结点标号”abc”三个字母其中一个。
将标号为相同字母的结点连边，将所有标号为b的结点与其它标号的结点连边。
给出图的m个连边，求一种合法的标号方案，不存在输出’NO’。
\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)
题解
如果有一个点和其它点都有连边，将其标号b。
然后选择一个未被标号的点，标号为a，二分图染色。
最后验证一下即可。
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; bool e[505][505]; int v[505]; void solve(int x,int y) { for(int i=1;i<=n;i++) if(i!=x&&i!=y) { if(e[i][x])v[i]=1; if(e[i][y])v[i]=3; if(e[i][x]&&e[i][y])v[i]=2; } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u][v]=e[v][u]=1; } bool flag=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!e[i][j]) { v[i]=1;v[j]=3; solve(i,j); flag=1; break; } if(!flag)for(int i=1;i<=n;i++)v[i]=1; for(int i=1;i<=n;i++)if(!v[i]){puts("No");return 0;} for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(abs(v[i]-v[j])<=1&&!e[i][j]){puts("No");return 0;} if(abs(v[i]-v[j])==2&&e[i][j]){puts("No");return 0;} } puts("Yes"); for(int i=1;i<=n;i++) printf("%c",'a'+v[i]-1); printf("\n"); return 0; |
449B.Jzzhu and Cities
n个点，m条带权边的无向图，另外还有k条特殊边，每条边连接1和i。
求可以删除这k条边中的多少条，使得每个点到1的最短距离不变。
\(1\leq n,m,K\leq 10^5\)
题解
求1到所有结点的最短路，对于每条特殊边1到x:
若其长度大于dis(x)，删除。
否则考察所有非特殊边x-y,若dis(y)+w=dis(x)，删除。
否则需要保存一条长度为dis(x)的边。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int n,m,k,cnt,ans; ll dis[100005]; int last[100005],q[100005]; bool inq[100005],mark[100005]; struct data{int to,next,v;bool flag;}e[1000005]; struct train{int x,y;}t[100005]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void ins(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; } inline void insert(int u,int v,int w) { ins(u,v,w);ins(v,u,w); } void spfa() { for(int i=1;i<=n;i++)dis[i]=1e60; dis[1]=0;q[0]=1;inq[1]=1; int head=0,tail=1; while(head!=tail) { int now=q[head];head++;if(head==100001)head=0; for(int i=last[now];i;i=e[i].next) if(dis[now]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]) { inq[e[i].to]=1; if(dis[e[i].to]<dis[q[head]]) { head--; if(head==-1)head=100000; q[head]=e[i].to; } else q[tail++]=e[i].to; if(tail==100001)tail=0; } } inq[now]=0; } } void sol(int x,int y) { for(int i=last[x];i;i=e[i].next) if(dis[e[i].to]+e[i].v==dis[x]) {ans++;return;} } int main() { n=read();m=read();k=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } for(int i=1;i<=k;i++) { t[i].x=read(),t[i].y=read(); ins(1,t[i].x,t[i].y); } spfa(); for(int i=1;i<=k;i++) { int x=t[i].x,y=t[i].y; if(mark[x]||y>dis[x]){ans++;continue;} else sol(x,y); mark[x]=1; } printf("%d",ans); return 0; } |
543B.Destroying Roads
n个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。
\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)
题解
其实就是问，至少需要多少条边，才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。
如果这两条路径不相交，那么答案为dis(s1,t1)+dis(s2,t2)。
如果相交部分为(p1,p2)，答案为p1,p2的最短路，加上p1,p2到其它4个点的最短路。
预处理任意点对距离，枚举两条路径重叠部分。
|
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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt; int last[3005],q[3005],dis[3005][3005]; int s1,t1,l1,s2,t2,l2; bool vis[3005]; struct edge{ int to,next; }e[6005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } void bfs(int x) { memset(vis,0,sizeof(vis)); int head=0,tail=1; q[0]=x;vis[x]=1; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(!vis[e[i].to]) { vis[e[i].to]=1; dis[x][e[i].to]=dis[x][now]+1; q[tail++]=e[i].to; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)bfs(i); s1=read();t1=read();l1=read(); s2=read();t2=read();l2=read(); if(dis[s1][t1]>l1||dis[s2][t2]>l2){puts("-1");return 0;} int ans=dis[s1][t1]+dis[s2][t2]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][i]+dis[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2]); if(dis[s1][j]+dis[i][j]+dis[i][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][j]+dis[s2][i]+dis[i][j]+dis[i][t1]+dis[j][t2]); } printf("%d\n",m-ans); return 0; } |
计数器 9862458
OI 课件=>
OI 课件=>
黄学长啊……510A那题应该是510C……
ok