锐客网

  1. 首页 > it技术 > >

csp突击图论题目

【csp突击图论题目】//BFS 求第一个点到最后一个点的最短路

#include using namespace std; const int N=1e5+10,M=2*N; int n,m,h[N],e[M],ne[M],idx,d[N]; //n个点m条边 void add(int a,int b){//a和b之间加边 e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int bfs(){ memset(d,-1,sizeof(d)); queue q; d[1]=0; q.push(1); while(!q.empty()){ int t=q.front(); q.pop(); for(int i=h[t]; i!=-1; i=ne[i]){ int j=e[i]; if(d[j]==-1){ d[j]=d[t]+1; q.push(j); } } } return d[n]; } int main(){ cin>>n>>m; memset(h,-1,sizeof(h)); for(int i=0; i>a>>b; add(a,b); } cout<

//判断有向图是否存在拓扑排序
#include #include #include #include using namespace std; const int N = 1e5 + 10; int e[N],ne[N],h[N],idx,d[N],n,m,top[N],cnt = 1; // e,ne,h,idx 邻接表模板 void add(int a,int b){// d 代表每个元素的入度 e[idx] = b; // top是拓扑排序的序列，cnt代表top中有多少个元素 ne[idx] = h[a]; h[a] = idx ++; } bool topsort(){ queue q; int t; for(int i = 1; i <= n; ++i)// 将所有入度为0的点加入队列 if(d[i] == 0) q.push(i); while(q.size()){ t = q.front(); //每次取出队列的首部 top[cnt] = t; //加入到 拓扑序列中 cnt ++; // 序列中的元素 ++ q.pop(); for(int i = h[t]; i != -1; i = ne[i]){// 遍历 t 点的出边 int j = e[i]; d[j] --; // j 的入度 -- if(d[j] == 0) q.push(j); //如果 j 入度为0，加入队列当中 } } if(cnt < n) return 0; else return 1; } int main(){ int a,b; cin >> n >> m; memset(h,-1,sizeof h); while(m--){ cin >> a >> b; add(a,b); d[b] ++; // a -> b , b的入度++ } if(topsort() == 0) cout << "-1"; else { for(int i = 1; i <= n; ++i){ cout << top[i] <<" "; } } return 0; }

//迪杰斯特拉求最短路
#include #include #include #include using namespace std; typedef pair PII; const int N=100010; int h[N],e[N],ne[N],idx,w[N]; int dist[N]; bool st[N]; int n,m; void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int dijktra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; priority_queue,greater>heap; heap.push({0,1}); while(heap.size()){ auto t=heap.top(); heap.pop(); int ver=t.second,distance=t.first; if(st[ver])continue; for(int i=h[ver]; i!=-1; i=ne[i]){ int j=e[i]; if(dist[j]>distance+w[i]){ dist[j]=distance+w[i]; heap.push({dist[j],j}); } } } if(dist[n]==0x3f3f3f3f)return -1; return dist[n]; }int main(){ memset(h,-1,sizeof h); cin>>n>>m; while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } cout<

//有边数限制的最短路
#include #include #include using namespace std; const int N = 510, M = 10010; int n, m, k; int dist[N], backup[N]; struct Edge{ int a, b, w; }edges[M]; int bellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i ++ ){ memcpy(backup, dist, sizeof dist); for (int j = 0; j < m; j ++ ){ int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (backup[a] != 0x3f3f3f3f && dist[b] > backup[a] + w){ dist[b] = backup[a] + w; } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main(){ scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i ++ ){ int a, b, w; scanf("%d%d%d", &a, &b, &w); edges[i] = {a, b, w}; } int t = bellman_ford(); if (t == -1) puts("impossible"); else printf("%d\n", t); return 0; }

//Floyd算法求任意两点最短路
#include using namespace std; const int N = 210, M = 2e+10, INF = 1e9; int n, m, k, x, y, z; int d[N][N]; void floyd() { for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } int main() { cin >> n >> m >> k; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i == j) d[i][j] = 0; else d[i][j] = INF; while(m--) { cin >> x >> y >> z; d[x][y] = min(d[x][y], z); //注意保存最小的边 } floyd(); while(k--) { cin >> x >> y; if(d[x][y] > INF/2) puts("impossible"); //由于有负权边存在所以约大过INF/2也很合理 else cout << d[x][y] << endl; } return 0; }

//求图的最小生成树
#include using namespace std; const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f; int n,m; int fa[N]; structEdge{ int a,b,w; bool operator<(const Edge &W)const{return w>n>>m; for(int i=0; i>a>>b>>c; edges[i]={a,b,c}; } int ans=kruskal(); if(ans==INF)puts("impossible"); else cout<

//二分图的最大匹配
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。 #include #include using namespace std; const int N = 510 , M = 100010; int n1,n2,m; int h[N],ne[M],e[M],idx; bool st[N]; int match[N]; void add(int a , int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void init(){ memset(h,-1,sizeof h); } int find(int x){//遍历自己喜欢的女孩 for(int i = h[x] ; i != -1 ; i = ne[i]) { int j = e[i]; if(!st[j]){//如果在这一轮模拟匹配中,这个女孩尚未被预定 st[j] = true; //那x就预定这个女孩了 if(!match[j]||find(match[j])) {//如果女孩j没有男朋友， match[j] = x; //或者她原来的男朋友能够预定其它喜欢的女孩。配对成功 return true; } } }//自己中意的全部都被预定了。配对失败。 return false; } int main(){ init(); cin>>n1>>n2>>m; while(m--) { int a,b; cin>>a>>b; add(a,b); } int res = 0; for(int i = 1; i <= n1 ; i ++){//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化 memset(st,false,sizeof st); if(find(i)) res++; } cout<

    推荐阅读


    上一篇：数据库|Qt数据库，查询表的内容，获取查询结果的行数和列数

    下一篇：如果你负责一款DAU（日活用户数量）1000W左右的陌生交友类社交产品，你会怎样从用户角度分析变现空间（）