时间限制: 1 Sec 内存限制: 128 MB
给定有向图 G,以及原点 S,请求出原点到所有点的最短路径。
输入文件的第一行包含两个整数 n, m,代表图中的顶点数和边数。
接下来 m 行,每行三个整数 u, v, w,代表一条从 u 指向 v,权值 为 w 的边。
最后一行为一个整数 S。
输出 n 个整数,依次代表 S 到 1, 2, . . . , n 的最短距离, S 到自己的距 离定义为 0,对于无法从 S 到达的点输出 -1。整数用一个空格隔开。
3 3 1 2 1 2 3 2 1 3 1 1
0 1 1
对于100%的数据,n ≤ 100000,m ≤ 800000,0 ≤ w ≤ 1000,请使用 dijkstra 算法。
Dijkstra 算法的每一次迭代分为两个步骤:选出当前距离最小的点和 从该点更新其他点的当前最小距离。很明显,第一步可以利用堆来选择, 时间复杂度降至 log(n),而第二步则可能会更改堆中的某些点的权值,这 时有两种处理方法,第一是额外记录每个点在堆中的位置并维护;第二是 直接将一个新结点插入堆中,因为新结点比老结点的权值更小一定在老结 点之前到达堆顶,所以这样做没有问题,当以后碰到堆顶结点为最短距离 已确定的结点,简单地将其丢弃即可,时间复杂度仅上升一个常数,是一 个不错的偷懒方法。
dijkstra+堆
#include<cstdio> #include<queue> using namespace std; int read() { int ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar(); return ret; } const int N=1e6+5; int n,m,d[N],s; bool fl[N]; int cnt,he[N],to[N],nxt[N],w[N]; inline void add(int u,int v,int k) { to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt,w[cnt]=k; } struct NA{ int id,x; }; bool operator >(NA i,NA j) { return i.x>j.x; } priority_queue<NA,vector<NA>,greater<NA> >q; int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),k=read(); add(u,v,k); } s=read(); for(int i=1;i<=n;i++) d[i]=2e9; q.push((NA){s,d[s]=0}); for(int i=1;i<=n;i++) { while(!q.empty()&&fl[q.top().id]) q.pop(); if(q.empty()) break; int u=q.top().id; fl[u]=1; q.pop(); for(int e=he[u];e;e=nxt[e]) { int v=to[e]; if(!fl[v]&&d[v]>d[u]+w[e]) q.push((NA){v,d[v]=d[u]+w[e]}); } } for(int i=1;i<n;i++) if(d[i]!=2e9) printf("%d ",d[i]); else printf("-1 "); if(d[n]!=2e9) printf("%d",d[n]); else printf("-1"); return 0; }时间限制: 1 Sec 内存限制: 128 MB
给定有向图 G,以及原点 S,请求出原点到所有点的最短路径。
输入文件的第一行包含两个整数 n, m,代表图中的顶点数和边数。
接下来 m 行,每行三个整数 u, v, w,代表一条从 u 指向 v,权值 为 w 的边。
最后一行为一个整数 S。
若图中存在负权环,则输出一行“ERROR”。
否则输出 n 个整数,依次代表 S 到 1, 2, . . . , n 的最短距离, S 到自己 的距离定义为 0,对于无法从 S 到达的点输出 -1。整数用一个空格隔开。
对于所有数据, n ≤ 1000, m ≤ 100000, −1000 ≤ w ≤ 1000。
SPFA模拟题
#include<cstdio> using namespace std; const int N=4e6+5; int n,m,s,l,r,q[N],dis[N],num[N]; bool fl[N]; int cnt,to[N],nxt[N],he[N],w[N]; inline void add(int u,int v,int k) { to[++cnt]=v,nxt[cnt]=he[u], w[cnt]=k,he[u]=cnt; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,k; scanf("%d%d%d",&u,&v,&k); add(u,v,k); } scanf("%d",&s); for(int i=1;i<=n;i++) dis[i]=1e9; int l=1,r=1; q[1]=s; dis[s]=0; fl[s]=1; num[s]=1; while(l<=r) { int u=q[l]; l++; fl[u]=0; for(int e=he[u];e;e=nxt[e]) { int v=to[e]; if(dis[v]>dis[u]+w[e]) { dis[v]=dis[u]+w[e]; if(!fl[v]) { fl[v]=1; num[v]++; if(num[v]==n) { puts("ERROR"); return 0; } q[++r]=v; } } } } for(int i=1;i<=n;i++) printf("%d%c",(dis[i]==1e9)?-1:dis[i],i==n?'\n':' '); return 0; }
时间限制: 1 Sec 内存限制: 128 MB
给定一个带权无向图 G = (V, E),请求出其中的最小圈。圈定义为 顶点序列 (v1,v2,...,vp,vp+1),满足 vi = vj(i = j), v1 = vp+1,且边 (vi, vi+1) ∈ E。
第一行为两个整数 n,m,代表图的顶点数和边数。
接下来 m 行,每行三个整数 u,v,w,描述一条连接 u 和 v,权值为 w 的边。
6 7 1 2 1 2 4 2 4 6 3 5 6 4 3 5 5 3 4 2 1 3 6
11
对于30%的数据n ≤ 30 对于 60% 的数据, n ≤ 100 对于 100% 的数据, n ≤ 400, w ≤ 100000
利用 Floyd 算法,求得环中的点最大编号为 1, 2, . . . , n 时的最小环。
模板题
#include<cstdio> #include<iostream> using namespace std; int read() { int ret=0; char ch=getchar(); bool f=0; while(ch<'0'||ch>'9') { if(ch=='-') f=1; ch=getchar(); } while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar(); return f?-ret:ret; } const int N=405; int n,m,f[N][N],a[N][N][2],ans; int main() { n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j][0]=a[i][j][1]=f[i][j]=6e8; for(int i=1;i<=n;i++) f[i][i]=0; ans=2e9; for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); f[u][v]=f[v][u]=min(f[u][v],w); if(a[u][v][0]!=6e8) a[u][v][0]=a[v][u][0]=w; else if(a[u][v][1]!=6e8) a[u][v][1]=a[v][u][1]=w; else { if(a[u][v][0]>w) a[u][v][1]=a[v][u][1]=a[u][v][1],a[u][v][0]=a[v][u][0]=w; else a[u][v][1]=a[v][u][1]=min(a[u][v][1],w); } ans=min(ans,a[u][v][0]+a[u][v][1]); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i!=j&&f[i][j]!=6e8&&a[i][k][0]!=6e8&&a[j][k][0]!=6e8) ans=min(ans,f[i][j]+a[i][k][0]+a[k][j][0]); f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } printf("%d",ans); return 0; }
时间限制: 1 Sec 内存限制: 128 MB
有 n 个城市需要用道路连接起来,现在有 m 条道路的修建方案,每 个方案的实施可以带来一定的利润,你的任务是确定实施的方案,使得任 意两个城市都连通,并且获得的利润最大。
第一行为两个整数 n, m,含义如题中所述。n ≤ 10000, m ≤ 200000。
接下来有 m 行,每行三个整数 u, v, w,代表在 u 和 v 之间修建一 条道路可以获得 w 的利润。注意,修建一条道路可能会导致亏损,这时我 们用负的利润表示。
3 3 1 2 -1 2 3 -2 1 3 -1
-2
>=0的边全部加上，其余的最大生成树处理
#include<cstdio> #include<algorithm> #define ll long long using namespace std; int read() { int ret=0; char ch=getchar(); bool f=0; while(ch<'0'||ch>'9') { if(ch=='-') f=1; ch=getchar(); } while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar(); return f?-ret:ret; } const int N=1e6+5; int n,m,ff[N]; ll ans; struct NA{ int u,v,w; }e[N]; bool cmp(NA i,NA j) { return i.w>j.w; } int find(int x) { return x==ff[x]?x:ff[x]=find(ff[x]); } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read(); sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) ff[i]=i; for(int i=1;i<=m;i++) if(e[i].w>=0) { int u=e[i].u,v=e[i].v; int f1=find(u),f2=find(v); ans+=e[i].w,ff[f1]=f2; } else { int u=e[i].u,v=e[i].v; int f1=find(u),f2=find(v); if(ff[f1]!=f2) ans+=e[i].w,ff[f1]=f2; } printf("%lld",ans); return 0; }
时间限制: 1 Sec 内存限制: 128 MB
在 JSOI2005 夏令营快要结束的时候,很多营员提出来要把整个夏令 营期间的资料刻录成一张光盘给大家,以便大家回去后继续学习。组委会 觉得这个主意不错!可是组委会一时没有足够的空光盘,没法保证每个人 都能拿到刻录上资料的光盘,又来不及去买了,怎么办呢?!
组委会把这个难题交给了 LHC,LHC 分析了一下所有营员的地域关 系,发现有些营员是一个城市的,其实他们只需要一张就可以了,因为一 个人拿到光盘后,其他人可以带着 U 盘之类的东西去拷贝啊!
可是,LHC 调查后发现,由于种种原因,有些营员并不是那么的合 作,他们愿意某一些人到他那儿拷贝资料,当然也可能不愿意让另外一些 人到他那儿拷贝资料,这与我们 JSOI 宣扬的团队合作精神格格不入!
现在假设总共有 N 个营员(2<=N<=2000),每个营员的编号为 1 N。 LHC 给每个人发了一张调查表,让每个营员填上自己愿意让哪些人到他那 儿拷贝资料。当然,如果 A 愿意把资料拷贝给 B,而 B 又愿意把资料拷 贝给 C,则一旦 A 获得了资料,则 B,C 都会获得资料。
现在,请你编写一个程序,根据回收上来的调查表,帮助 LHC 计算 出组委会至少要刻录多少张光盘,才能保证所有营员回去后都能得到夏令 营资料?
先是一个数 N,接下来的 N 行,分别表示各个营员愿意把自己获得的 资料拷贝给其他哪些营员。即输入数据的第 i+1 行表示第 i 个营员愿意把 资料拷贝给那些营员的编号,以一个 0 结束。如果一个营员不愿意拷贝资 料给任何人,则相应的行只有 1 个 0,一行中的若干数之间用一个空格隔 开。
5 2 4 3 0 4 5 0 0 0 1 0
1
tarjan缩点后统计度为0的结点
#include<cstdio> #include<iostream> using namespace std; int read() { int ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar(); return ret; } const int N=2005,M=4000005; int n,m,d[N],ans; int cnt,he[M],to[M],nxt[M]; struct NA{ int u,v; }e[M]; int sgn,dfn[N],low[N],top,st[N],col,co[N]; inline void add(int u,int v) { to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt; } void tar(int u) { dfn[u]=low[u]=++sgn; st[++top]=u; for(int e=he[u];e;e=nxt[e]) { int v=to[e]; if(!dfn[v]) tar(v),low[u]=min(low[u],low[v]); else if(!co[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { co[u]=++col; while(top&&st[top]!=u) co[st[top--]]=col; top--; } } int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); while(x) e[++m].u=i,e[m].v=x, add(i,x),x=read(); } for(int i=1;i<=n;i++) if(!dfn[i]) tar(i); for(int i=1;i<=m;i++) if(co[e[i].u]!=co[e[i].v]) d[co[e[i].v]]++; ans=0; for(int i=1;i<=col;i++) if(!d[i]) ans++; printf("%d",ans); return 0; }
时间限制: 1 Sec 内存限制: 128 MB
给定连通无向图 G,请求出 G 中的割点和桥的个数。
第一行两个整数 n,m,代表图的顶点数和边数。 接下来 m 行,每行两个整数 u, v,描述一条无向边。 N ≤ 50000, m ≤ 200000
输出两个整数,先输出割点的数量和再输出桥的数量,用一个空格隔 开。
4 5 1 2 1 2 2 3 2 3 3 4
2 1
#include<cstdio> #include<iostream> using namespace std; int read() { int ret=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar(); return ret; } const int N=1e6+5; int n,m,num[N],ans; int cnt,he[N],to[N],nxt[N]; int sgn,low[N],dfn[N]; inline void add(int u,int v) { to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt; } void tar1(int u,int r) { low[u]=dfn[u]=++sgn; int ch=0; for(int e=he[u];e;e=nxt[e]) { int v=to[e]; if(!dfn[v]) { tar1(v,r); low[u]=min(low[u],low[v]); if(u!=r&&low[v]>=dfn[u]) num[u]=1; if(u==r) ch++; } low[u]=min(low[u],dfn[v]); } if(u==r&&ch>=2) num[u]=1; } void tar2(int fa,int u) { low[u]=dfn[u]=++sgn; for(int e=he[u];e;e=nxt[e]) { int v=to[e]; if(v!=fa) { if(!dfn[v]) { tar2(u,v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) ans++; } low[u]=min(low[u],dfn[v]); } else fa=0; } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); add(u,v); add(v,u); } tar1(1,1); for(int i=1;i<=n;i++) if(num[i]) ans++; printf("%d ",ans); sgn=ans=0; for(int i=1;i<=n;i++) dfn[i]=low[i]=0; tar2(0,1); printf("%d",ans); return 0; }
