板子

#include <iostream> #include <stdio.h> #include <string> #include<cstring> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6+5; // 一. 图论 //Dijkstra 过程 //1.选定一个点，a. 未被选过 // b.距离最短 //2.对于这个点的所有邻近点去尝试松弛 /* Dijkstra 过程 1.选定一个点，a. 未被选过 b.距离最短 2.对于这个点的所有邻近点去尝试松弛 vector<int>dij(vector<vector<int>>G,int s) { int n=G.size(); vector<int >dis(n,INF); vector<int>vis(n,false); dis[s]=0; for(int i=0;i<n-1;i++) { int node=-1; for(int j=0;j<n;j++) //选定一个点.(a.未被选过,b.距离最短) if(!vis[j]&&(node==-1||dis[j]<dis[node])) node=j; for(int j=0;j<n;j++) //2.对于这个点的所有邻近点去尝试松弛 dis[j]=min(dis[j],dis[node]+G[node][j]); vis[node]=true; } return dis; } vector<int>Dij(vector<vector<int>>G,int s) { int n=G.size(); vector<int>dis(n,INF); vector<int>vis(n,false); dis[s]=0; for(int i=0;i<n-1;i++) { int node=-1; for(int j=0;j<n;j++) if(!vis[j]&&(dis[j]<dis[node]||node==-1)) node=j; for(int j=0;j<n;j++) dis[j]=min(dis[j],dis[node]+G[node][j]); vis[node]=true; } return dis; } int main() { int m,n; while (~scanf("%d%d",&n,&m)){ if(n==0&&m==0) return 0; vector<vector<int>>G(n,vector<int>(n)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) G[i][j]=INF; for(int i=1,a,b,c;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); if(G[a-1][b-1]==INF) G[a-1][b-1]=G[b-1][a-1]=c; if(G[a-1][b-1]>c) G[a-1][b-1]=G[b-1][a-1]=c; } auto dis=Dij(G,0); cout<<dis[n-1]<<endl; } return 0; } // Dij+;链式前向星+堆优化 浴谷P4779 【模板】单源最短路径（标准版） struct Edge{ int to,next,w; }edge[maxn]; int tot,head[maxn],dis[maxn]; bool vis[maxn]; void add(int u,int v,int val) { edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=val; head[u]=tot++; } struct node{ int dis,pos; bool operator<(const node &x)const{ return x.dis<dis;//大根堆，大的在前 } }; priority_queue<node>q;//定义一个大根堆 int n,m,s; void Dij() { dis[s]=0; q.push(node{0,s}); while (!q.empty()) { //如果堆栈为空，那么所有点都已经更新 node tmp=q.top(); q.pop(); int x=tmp.pos; //记录堆顶并将其弹出 if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ //搜索堆顶所有的连边 int y=edge[i].to; if(dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; //松弛操作 if(!vis[y]) q.push(node{dis[y],y}); //把新遍历的到的点加入堆中 } } } } int main() { scanf("%d%d%d",&n,&m,&s); memset(head,-1,sizeof(head)); for(int i=0;i<maxn;i++)dis[i]=2147483647; memset(vis,false,sizeof(vis)); for(int i=0,u,v,w;i<m;i++) scanf("%d%d%d",&u,&v,&w),add(u,v,w); Dij(); for(int i=1;i<=n;i++){ printf("%d ",dis[i]); } return 0; } //poj 1511 Dij+堆优化 struct Edge{ int to,next,w; }edge[maxn]; int head[maxn],tot=0,n,m,t; int u[maxn],v[maxn],w[maxn]; void add_edge(int u,int v,int w) { edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=w; head[u]=tot++; } struct node{ int dis,pos; bool operator<(const node &x)const{ return x.dis<dis; } }; priority_queue<node>q; int dis[maxn]; bool vis[maxn]; void Dij(int s) { memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; q.push(node{0,s}); while (!q.empty()) { node tmp=q.top(); q.pop(); int x=tmp.pos; if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; if(!vis[y]) q.push(node{dis[y],y}); } } } } int main() { scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]),add_edge(u[i],v[i],w[i]); Dij(1); ll ans=0; for(int i=2;i<=n;i++) ans+=dis[i]; tot=0; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) add_edge(v[i],u[i],w[i]); Dij(1); for(int i=2;i<=n;i++) ans+=dis[i]; printf("%lld\n",ans); } return 0; } // 浴谷 P1629 int n,m; int u[maxn],v[maxn],w[maxn]; struct Edge{ int to,next,w; }edge[maxn]; int head[maxn],tot; void add(int u,int v,int w) { edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=w; head[u]=tot++; } void init(){ memset(head,-1,sizeof(head)),tot=0; } struct node{ int dis,pos; bool operator<(const node &x)const { return x.dis<dis; } }; int dis[maxn]; bool vis[maxn]; priority_queue<node>q; void Dijskra(int s) { memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; q.push(node{0,s}); while (!q.empty()){ node tmp=q.top(); q.pop(); int x=tmp.pos; if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; if(!vis[y]) q.push(node{dis[y],y}); } } } } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]),add(u[i],v[i],w[i]); int ans=0; Dijskra(1); for(int i=2;i<=n;i++) ans+=dis[i]; init(); for(int i=1;i<=m;i++) add(v[i],u[i],w[i]); Dijskra(1); for(int i=2;i<=n;i++) ans+=dis[i]; printf("%d\n",ans); return 0; }*/ // Prim+最小生成树模板 /* int n,mp[maxn][maxn],dis[maxn]; bool vis[maxn]; void Prim() { memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); int cou=1,sum=0; for(int i=1;i<=n;i++)dis[i]=mp[1][i]; dis[1]=0,vis[1]=true; for(int i=1;i<n;i++,cou++){ int now=INF,Max=INF; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]<Max) Max=dis[j],now=j; if(now==INF) break; vis[now]=true; sum+=Max; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]>mp[now][j]) dis[j]=mp[now][j]; } printf("%d\n",sum); } int main() { while (~scanf("%d",&n)&&n) { int m=n*(n-1)/2; memset(mp,INF,sizeof(mp)); for(int i=1,a,b,val;i<=m;i++){ scanf("%d%d%d",&a,&b,&val); if(val<mp[a][b]) mp[a][b]=mp[b][a]=val; } Prim(); } return 0 } */ /* int n,m,ans=0,mat[maxn][maxn],vis[maxn],dis[maxn]; void Prim() { dis[1]=0; for(int i=1;i<=n;i++){ int now=-1; for(int j=1;j<=n;j++) if(!vis[j]&&(now==-1||dis[now]>dis[j])) now=j; ans+=dis[now]; vis[now]=true; for(int j=1;j<=n;j++) if(!vis[j]) dis[j]=min(dis[j],mat[now][j]); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mat[i][j]); memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); Prim(); printf("%d\n",ans); return 0; }*/ // 最小生成树二·Kruscal算法 /* int n,m; struct Edge{ int from,to,val; }edge[maxn]; bool cmp(Edge a,Edge b){ return a.val<b.val; } int pre[maxn]; int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]); } void Union(int x,int y){ pre[find(x)]=find(y); } int main() { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) pre[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val); sort(edge+1,edge+m+1,cmp); int ans=0; for(int i=1;i<=m;i++){ if(find(edge[i].from)!=find(edge[i].to)) ans+=edge[i].val,Union(edge[i].from,edge[i].to); } printf("%d\n",ans); return 0; }*/ // HDU 1232 并查集 /* int n,m,pre[maxn]; int find(int x){ if(x!=pre[x]) return pre[x]=find(pre[x]); return pre[x]; } void Union(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) pre[find(x)]=y; } int main() { while (~scanf("%d%d",&n,&m)&&n) { for(int i=1;i<=n;i++)pre[i]=i; for(int i=1,a,b;i<=m;i++){ scanf("%d%d",&a,&b); if(find(a)!=find(b)) Union(a,b); } int ans=0; for(int i=1;i<=n;i++) if(pre[i]==i) ans++; printf("%d\n",ans-1); } return 0; }*/ // HDU 2063 匈牙利算法+链式前向星遍历 /* int k,n,m,tot,head[maxn],nxt[maxn]; bool vis[maxn]; struct Edge{ int to,next; }edge[maxn]; void add_edge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } bool find(int x){ for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]==0){ vis[v]=true; if(nxt[v]==0||find(nxt[v])){ nxt[v]=x; return true; } } } return false; } int match() { int ans=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans; } int main() { while (~scanf("%d",&k)&&k){ scanf("%d%d",&n,&m); tot=0; memset(nxt,0,sizeof(nxt)); memset(head,-1,sizeof(head)); for(int i=1,u,v;i<=k;i++) scanf("%d%d",&u,&v),add_edge(u,v); printf("%d\n",match()); } return 0; } int n,m,k,nxt[maxn]; bool vis[maxn]; struct Edge{ int to,next; }edge[maxn]; int tot,head[maxn]; void add_edge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } bool find(int u) { for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]){ vis[v]=1; if(nxt[v]==0||find(nxt[v])){ nxt[v]=u; return true; } } } return false; } int match() { int ans=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans; } int main() { while (~scanf("%d",&k)&&k){ scanf("%d%d",&n,&m); tot=0; memset(nxt,0,sizeof(nxt)); memset(head,-1,sizeof(head)); for(int i=1,u,v;i<=k;i++) cin>>u>>v,add_edge(u,v); cout<<match()<<endl; } }*/ /* //HDU 4619 建边+匈牙利 struct Edge{ int to,next; }edge[maxn]; int tot,head[maxn]; int n,m; void add_edge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } pair<int,int>p2[maxn]; pair<int,int>p1[maxn]; bool vis[maxn]; int nxt[maxn]; bool find(int u){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]){ vis[v]=true; if(nxt[v]==0||find(nxt[v])){ nxt[v]=u; return true; } } } return false; } // 第二次看是真的理解了吧 // 移去部分骨牌，使留下不会相互覆盖的骨牌数量最多(同方向骨牌不会相互覆盖) // 分析：ans=n+m-不同方向的最大匹配数 int match(){ int ans=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans; } int main() { while (~scanf("%d%d",&n,&m)&&n&&m){ memset(head,-1,sizeof(head)); memset(nxt,0,sizeof(nxt)); for(int i=1,x,y;i<=n;i++) cin>>x>>y,p1[i]=make_pair(x,y); for(int i=1,x,y;i<=m;i++) cin>>x>>y,p2[i]=make_pair(x,y); /*相互覆盖的部分建边，题目给出：n块 (x1,y1)(x1+1,y1)规格的的骨牌 m块(x2,y2)(x2,y2+1) 规格的骨牌 有四种覆盖的情况：(x1,y1)与(x2,y2),(x1,y1)与(x2,y2+1) (x1+1,y1)与(x2,y2),(x1+1,y1)与(x2,y2+1) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int a=p1[i].first,b=p1[i].second; int c=p2[j].first,d=p2[j].second; if((a==c&&b==d)||(a==c&&b==d+1)||(b==d&&c==a+1)||(c==a+1&&b==d+1)) add_edge(i,j); } printf("%d\n",n+m-match()); } return 0; }*/ // HDU 1845 匈牙利（卡常） /* int n,m,t; struct Edge{ int to,next; }edge[maxn*3]; int head[maxn],tot; void add_edge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } bool vis[maxn]; int nxt[maxn]; int find(int u){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]){ vis[v]=1; if(nxt[v]==0||find(nxt[v])){ nxt[v]=u; return true; } } } return false; } int match() { int ans=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans; } int u,v; int main() { scanf("%d",&t); while (t--){ scanf("%d",&n); memset(head,-1,sizeof(head)); memset(nxt,0,sizeof(nxt)); tot=0; m=3*n/2; while (m--) { scanf("%d%d", &u, &v), add_edge(u, v), add_edge(v, u); } printf("%d\n",match()/2); } } */ // Dijskra+堆优化+链式前向星 /* struct Edge{ int to,next,val; }edge[maxn]; int head[maxn],tot; void add_edge(int u,int v,int val){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].val=val; head[u]=tot++; } int m,n,dis[maxn]; bool vis[maxn]; struct node{ int dis,pos; bool operator<(const node &x)const { return x.dis<dis; } }; priority_queue<node>q; void Dijskra(int s) { memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; q.push(node{0,s}); while (!q.empty()){ node tmp=q.top(); q.pop(); int x=tmp.pos; if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val){ dis[y]=dis[x]+edge[i].val; if(!vis[y]) q.push(node{dis[y],y}); } } } } int main() { scanf("%d%d",&m,&n); memset(head,-1,sizeof(head)); for(int i=1,u,v,w;i<=m;i++) scanf("%d%d%d",&u,&v,&w),add_edge(u,v,w),add_edge(v,u,w); Dijskra(1); printf("%d\n",dis[n]); return 0; }*/ // 字符串 // KMP 模板 HDU 1711 POJ 3461 /* int n,m; int a[maxn],b[maxn],Next[maxn]; void Next_pre() { for(int i=1,j=0;i<m;i++){ while (j&&b[i]!=b[j]) j=Next[j-1]; if(b[i]==b[j]) j++; Next[i]=j; } } int KMP_match(int s) { Next_pre(); for(int i=s,j=0;i<n;i++){ while (j&&a[i]!=b[j]) j=Next[j-1]; if(a[i]==b[j]) j++; if(j==m) return i-m+1+1; } return -1; } int main() { int t; cin>>t; while (t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d",&b[i]); printf("%d\n",KMP_match(0)); } return 0; } int n,Next[maxn],lp,ls; char p[maxn],s[maxn]; void Next_pre() { for(int i=1,j=0;i<lp;i++){ while (j&&p[j]!=p[i]) j=Next[j-1]; if(p[i]==p[j]) j++; Next[i]=j; } } int KMP_match(int begin){ int ans=0; Next_pre(); for(int i=begin,j=0;i<ls;i++){ while (j&&s[i]!=p[j]) j=Next[j-1]; if(p[j]==s[i]) j++; if(j==lp) ans++; } return ans; } int main() { scanf("%d",&n); while (n--){ scanf("%s%s",p,s); ls=strlen(s),lp=strlen(p); printf("%d\n",KMP_match(0)); } return 0; }*/ // HDU 3336 Next数组的理解 /* int t,n,Next[maxn]; char p[maxn]; int Next_pre() { // 一个字符串（长度为n）本身有n个前缀，Next记录了最长前后缀，只要Next不为0，说明存在 // 一个后缀与前缀相同 memset(Next,0,sizeof(Next)); for(int j=0,i=1;i<n;i++){ while (j&&p[i]!=p[j]) j=Next[j-1]; if(p[i]==p[j]) j++; Next[i]=j; } int ans=0; for(int i=0;i<n;i++) if(Next[i]) ans++; return ans+n; } int main() { int t; cin>>t; while (t--){ cin>>n>>p; printf("%d\n",Next_pre()%10007); } return 0; }*/ // HDU - 3746 字符串最小循环节问题 /* int n,ls,Next[maxn]; char s[maxn]; int Next_pre() { memset(Next,0,sizeof(Next)); for(int i=1,j=0;i<ls;i++){ while (j&&s[i]!=s[j]) j=Next[j-1]; if(s[i]==s[j]) j++; Next[i]=j; } int len=ls-Next[ls-1]; if(Next[ls-1]==0) return ls; if(ls%len!=0) return len-ls%len; else return 0; } int main() { std::ios::sync_with_stdio(false); cin>>n; while (n--){ cin>>s; ls=strlen(s); cout<<Next_pre()<<endl; } }*/ // 判断回文串（单哈希，双哈希）取模才能过？ /* int n; int main() { while (~scanf("%d",&n)){ ull hash1=0,hash2=0,X=31,x=2333,mod=1e9+7,h1=0,h2=0; char s=getchar(); for(int i=1;i<=n/2;i++){ char s=getchar(); hash1=(hash1*X+(ull)s)%mod; h1=(h1*x+(ull)s)%mod; } if(n&1)char s=getchar(); ull a=1,b=1; for(int i=1;i<=n/2;i++){ char s=getchar(); hash2=(hash2+(ull)s*a)%mod; h2=(h2+(ull)s*b)%mod; a=a*X%mod; b=b*x%mod; } if(hash2==hash1&&h1==h2) printf("YES\n"); else printf("NO\n"); } }*/