首页 > 其他 > 详细

从2017年暑假到现在手打的模板↑_↑

时间:2018-01-14 00:47:18      阅读:106      评论:0      收藏:0      [点我收藏+]

标签:turn   init   d+   cmp   push   typedef   for   jks   make   

一、

求逆元-费马小定理

 1 //amodm
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 typedef long long lol;
 7 
 8 int n,p;
 9 
10 lol qpow(lol x)
11 {
12 int y=p-2;
13 lol ans=1;
14 while (y) {
15 if (y&1) ans*=x,ans%=p;
16 x*=x;x%=p;y/=2;
17 }
18 return ans;
19 }
20 
21 inline void write(lol x)
22 {
23 if(x<0) putchar(-),x=-x;
24 if(x>9) write(x/10);
25 putchar(x%10+0);
26 }
27 
28 int main()
29 {
30 scanf("%d%d",&n,&p);
31 for (int i=1;i<=n;i++) {
32 write(qpow(i)%p);
33 putchar(\n);
34 }
35 return 0;
36 }

 

二、

树状数组

 1 //BIT
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 typedef long long lol;
 7 
 8  
 9 
10 lol n,m;
11 lol f[500010];
12 
13  
14 
15 lol lowbit(lol x)
16 {
17 return x&-x;
18 }
19 
20  
21 
22 void add(lol x,lol k)
23 {
24 for (int i=x;i<=n;i+=lowbit(i)) f[i]+=k;
25 }
26 
27  
28 
29 lol getsum(lol x)
30 {
31 lol ans=0;
32 for (int i=x;i;i-=lowbit(i)) ans+=f[i];
33 return ans;
34 }
35 
36  
37 
38 int main()
39 {
40 cin>>n>>m;lol a;
41 for (int i=1;i<=n;i++) scanf("%lld",&a),add(i,a);
42 lol flag,x,y,k;
43 for (int i=1;i<=m;i++) {
44 scanf("%lld%lld",&flag,&x);
45 if (flag==1) {
46 scanf("%lld",&k);
47 add(x,k);
48 }
49 if (flag==2) {
50 scanf("%lld",&y);
51 printf("%lld\n",getsum(y)-getsum(x-1));
52 }
53 }
54 return 0;
55 }

 

三、

最大流-Dinic

 1 //dinic
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 using namespace std;
 7 
 8  
 9 
10 int cnt=-1,depth[10010],cur[10010],s,t,n,m;
11 int next[200010],head[10010],v[200010],w[200010];
12 
13  
14 
15 int dfs(int u,int flow)
16 {
17 if (u==t) return flow;
18 for (int& i=cur[u];i!=-1;i=next[i]) {
19 if ((w[i]!=0)&&(depth[v[i]]==depth[u]+1)) {
20 int di=dfs(v[i],min(flow,w[i]));
21 if (di>0) {w[i]-=di;w[i^1]+=di;return di;}
22 }
23 }
24 return 0;
25 }
26 
27  
28 
29 bool bfs()
30 {
31 queue <int> q;
32 memset(depth,0,sizeof(depth));
33 while (!q.empty()) q.pop();
34 q.push(s);depth[s]=1;
35 do {
36 int u=q.front();q.pop();
37 for (int i=head[u];i!=-1;i=next[i]) {
38 if ((w[i]>0)&&(depth[v[i]]==0)) {
39 q.push(v[i]);depth[v[i]]=depth[u]+1;
40 }
41 }
42 }while(!q.empty());
43 if (depth[t]>0) return 1;
44 return 0;
45 }
46 
47  
48 
49 int dinic()
50 {
51 int ans=0;
52 while (bfs()) {
53 for (int i=1;i<=n;i++) cur[i]=head[i];
54 while (int d=dfs(s,3e8)) ans+=d;
55 }
56 return ans;
57 }
58 
59  
60 
61 int main()
62 {
63 int a,b,c;
64 cin>>n>>m>>s>>t;
65 memset(head,-1,sizeof(head));
66 memset(next,-1,sizeof(next));
67 while (m--) {
68 scanf("%d%d%d",&a,&b,&c);
69 cnt++;v[cnt]=b;w[cnt]=c;
70 next[cnt]=head[a];head[a]=cnt;
71 cnt++;v[cnt]=a;w[cnt]=0;
72 next[cnt]=head[b];head[b]=cnt;
73 }
74 cout<<dinic()<<endl;
75 return 0;
76 }

 

四、

二分图-匈牙利算法

 1 //eft_xyl
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7  
 8 
 9 int n,m,e,girl[1005];
10 bool used[1005],line[1005][1005];
11 
12  
13 
14 bool find(int x)
15 {
16 for (int j=1;j<=m;j++)
17 if (line[x][j]&&!used[j]) {
18 used[j]=1;
19 if (!girl[j]||find(girl[j])) {
20 girl[j]=x;return 1;
21 }
22 }
23 return 0;
24 }
25 
26  
27 
28 int main()
29 {
30 int x,y;
31 cin>>n>>m>>e;
32 for (int i=1;i<=e;i++)
33 scanf("%d%d",&x,&y),line[x][y]=1;
34 e=0;
35 for (int i=1;i<=n;i++) {
36 if (find(i)) e++;
37 memset(used,0,sizeof(used));
38 }
39 cout<<e<<endl;
40 return 0;
41 }

 

五、

扩展欧几里得

 1 //exgcd
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7  
 8 
 9 void exgcd(int a,int b,int &x,int &y)
10 {
11 if (!b) x=1,y=0;
12 else {
13 exgcd(b,a%b,y,x);
14 y-=x*(a/b);
15 }
16 }
17 
18  
19 
20 int main()
21 {
22 int a,b,x,y;
23 cin>>a>>b;
24 exgcd(a,b,x,y);
25 cout<<(x%b+b)%b<<endl;
26 return 0;
27 }

 

六、

假的字符串Hash,其实是map

 1 //jia de hash,zhe shi map!
 2 #include <map>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <iostream>
 7 using namespace std;
 8 
 9  
10 
11 int n;
12 string s;
13 map <string,int> mp;
14 
15  
16 
17 int main()
18 {
19 cin>>n;int ans=0;
20 for (int i=1;i<=n;i++) {
21 cin>>s;
22 if (!mp.count(s)) ans++,mp[s]=1;
23 }
24 cout<<ans<<endl;
25 return 0;
26 }

 

七、

克鲁斯卡尔

 1 //kruskal
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8  
 9 
10 int n,m;
11 int fa[5001];
12 
13  
14 
15 struct ed {
16 int f,t,w;
17 }e[400010];
18 
19  
20 
21 bool cmp(ed a,ed b)
22 {
23 return a.w<b.w;
24 }
25 
26  
27 
28 void init()
29 {
30 for (int i=1;i<=n;i++) fa[i]=i;
31 }
32 
33  
34 
35 int find(int a)
36 {
37 if (a==fa[a]) return a;
38 return fa[a]=find(fa[a]);
39 }
40 
41  
42 
43 void unionset(int a,int b)
44 {
45 int u=find(a),v=find(b);
46 if (u!=v) fa[u]=v;
47 }
48 
49  
50 
51 bool same(int u,int v)
52 {
53 return find(u)==find(v);
54 }
55 
56  
57 
58 void kruskal()
59 {
60 int res=0;
61 init();int cnt=0;
62 sort(e+1,e+1+m,cmp);
63 for (int i=1;i<=m;i++) {
64 if (!same(e[i].f,e[i].t)) {
65 res+=e[i].w;
66 unionset(e[i].f,e[i].t);
67 ++cnt;
68 }
69 if (cnt==n-1) break;
70 }
71 cout<<res<<endl;
72 }
73 
74  
75 
76 int main()
77 {
78 cin>>n>>m;int x,y,w;
79 for (int i=1;i<=m;i++) {
80 scanf("%d%d%d",&x,&y,&w);
81 e[i].f=x;e[i].t=y;e[i].w=w;
82 }
83 kruskal();
84 return 0;
85 }

 

八、

LCA-倍增

 1 //lca-ST
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7  
 8 
 9 int n,m,ss;
10 int dep[500010];
11 int dpt[500010][30];
12 
13  
14 
15 int cnt;
16 int o[1000010];
17 int s[1000010][2];
18 //lsqxx!!!
19 void jia(int x,int y)
20 {
21 s[++cnt][1]=o[x];
22 s[cnt][0]=y;o[x]=cnt;
23 }
24 
25  
26 
27 void dfs(int x,int d)
28 {
29 dep[x]=d;
30 for (int i=o[x];i;i=s[i][1]) {
31 int y=s[i][0];
32 if (!dep[y]) {
33 dpt[y][0]=x;
34 dfs(y,d+1);
35 }
36 }
37 }
38 
39  
40 
41 void init()
42 {
43 for (int j=1;j<=19;j++)
44 for (int i=1;i<=n;i++)
45 dpt[i][j]=dpt[dpt[i][j-1]][j-1];
46 }
47 
48  
49 
50 int lca(int a,int b)
51 {
52 if (dep[a]<dep[b]) swap(a,b);
53 for (int j=19;j>=0;j--)
54 if (dep[a]-(1<<j)>=dep[b]) a=dpt[a][j];
55 if (a!=b) {
56 for (int j=19;j>=0;j--)
57 if (dpt[a][j]!=dpt[b][j])
58 a=dpt[a][j],b=dpt[b][j];
59 a=dpt[a][0];
60 }
61 return a;
62 }
63 
64  
65 
66 int main()
67 {
68 int x,y;
69 cin>>n>>m>>ss;
70 for (int i=1;i<n;i++) {
71 scanf("%d%d",&x,&y);
72 jia(x,y);jia(y,x);
73 }
74 dfs(ss,1);init();
75 for (int i=1;i<=m;i++) {
76 scanf("%d%d",&x,&y);
77 printf("%d\n",lca(x,y));
78 }
79 return 0;
80 }

 

九、

构造最长公共子序列LCS

  1 //只能打印一个最长公共子序列
  2 #include <iostream>
  3 using namespace std;
  4 
  5 const int X = 100, Y = 100; //串的最大长度
  6 char result[X+1]; //用于保存结果
  7 int count=0; //用于保存公共最长公共子串的个数
  8 
  9  
 10 
 11 /*功能:计算最优值
 12 *参数:
 13 * x:字符串x
 14 * y:字符串y
 15 * b:标志数组
 16 * xlen:字符串x的长度
 17 * ylen:字符串y的长度
 18 *返回值:最长公共子序列的长度
 19 *
 20 */
 21 int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen) 
 22 {
 23 int i = 0;
 24 int j = 0;
 25 
 26  
 27 
 28 int c[X+1][Y+1];
 29 for (i = 0; i<=xlen; i++) 
 30 {
 31 c[i][0]=0;
 32 } 
 33 for (i = 0; i <= ylen; i++ ) 
 34 {
 35 c[0][i]=0;
 36 }
 37 for (i = 1; i <= xlen; i++) 
 38 {
 39 
 40 for (j = 1; j <= ylen; j++) 
 41 {
 42 if (x[i - 1] == y[j - 1])
 43 {
 44 c[i][j] = c[i-1][j-1]+1; 
 45 b[i][j] = 1;
 46 }
 47 else 
 48 if (c[i-1][j] > c[i][j-1]) 
 49 {
 50 c[i][j] = c[i-1][j]; 
 51 b[i][j] = 2;
 52 }
 53 else 
 54 if(c[i-1][j] <= c[i][j-1])
 55 {
 56 c[i][j] = c[i][j-1]; 
 57 b[i][j] = 3;
 58 }
 59 
 60 }
 61 }
 62 cout << "计算最优值效果图如下所示:" << endl;
 63 for(i = 1; i <= xlen; i++)
 64 {
 65 for(j = 1; j < ylen; j++)
 66 {
 67 cout << c[i][j] << " ";
 68 }
 69 cout << endl;
 70 }
 71 return c[xlen][ylen];
 72 }
 73 
 74 void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_Len)
 75 {
 76 if (i ==0 || j==0) 
 77 {
 78 return;
 79 }
 80 if(b[i][j]== 1) 
 81 { 
 82 current_Len--;
 83 result[current_Len]=x[i- 1];
 84 Display_Lcs(i-1, j-1, x, b, current_Len);
 85 }
 86 else 
 87 {
 88 if(b[i][j] == 2)
 89 {
 90 Display_Lcs(i-1, j, x, b, current_Len);
 91 }
 92 else 
 93 {
 94 if(b[i][j]==3)
 95 {
 96 Display_Lcs(i, j-1, x, b, current_Len);
 97 }
 98 else
 99 {
100 Display_Lcs(i-1,j,x,b, current_Len);
101 }
102 }
103 }
104 }
105 
106 int main(int argc, char* argv[])
107 {
108 string x = "ABCBDAB";
109 string y = "BDCABA";
110 int xlen = x.length();
111 int ylen = y.length();
112 
113  
114 
115 int b[X + 1][Y + 1];
116 
117  
118 
119 int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
120 cout << lcs_max_len << endl;
121 
122  
123 
124 Display_Lcs( xlen, ylen, x, b, lcs_max_len );
125 
126 //打印结果如下所示
127 for(int i = 0; i < lcs_max_len; i++)
128 {
129 cout << result[i];
130 }
131 cout << endl;
132 return 0;
133 }

 

十、

归并排序求逆序对

 1 //msort_nxd
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7  
 8 
 9 int ans,n,a[100010],r[100010];
10 
11  
12 
13 void msort_nxd(int s,int t)
14 {
15 if (s==t) return;
16 int mid=s+t>>1;
17 msort_nxd(s,mid);
18 msort_nxd(mid+1,t);
19 int i=s,j=mid+1,k=s;
20 while (i<=mid&&j<=t) {
21 if (a[i]<=a[j]) {
22 r[k]=a[i];i++;k++;
23 }
24 else {
25 r[k]=a[j];j++;k++;
26 ans+=mid-i+1;
27 }
28 }
29 while (i<=mid) r[k++]=a[i++];
30 while (j<=t) r[k++]=a[j++];
31 for (int q=s;q<=t;q++) a[q]=r[q];
32 }
33 
34  
35 
36 int main()
37 {
38 cin>>n;
39 for (int i=1;i<=n;i++) {
40 scanf("%d",&a[i]);
41 }
42 msort_nxd(1,n);
43 cout<<ans<<endl;
44 return 0;
45 }

 

十一、

线段树

 1 //segment
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #define ll(x) ((x)<<1)
 6 #define rr(x) ((x)<<1|1)
 7 using namespace std;
 8 typedef long long lol;
 9 
10  
11 
12 lol n,m,a[100010];
13 lol sgm[100010*4],lazy[100010*4];
14 
15  
16 
17 void shang(lol r)
18 {
19 sgm[r]=sgm[ll(r)]+sgm[rr(r)];
20 }
21 
22  
23 
24 void xia(lol r,lol z,lol y)
25 {
26 int k=z+y>>1;
27 lazy[ll(r)]+=lazy[r];
28 lazy[rr(r)]+=lazy[r];
29 sgm[ll(r)]+=(k-z+1)*lazy[r];
30 sgm[rr(r)]+=(y-k)*lazy[r];
31 lazy[r]=0;
32 }
33 
34  
35 
36 void js(lol r,lol z,lol y)
37 {
38 if (z==y) {
39 sgm[r]=a[z];
40 return;
41 }
42 int k=z+y>>1;
43 js(ll(r),z,k);
44 js(rr(r),k+1,y);
45 shang(r);
46 }
47 
48  
49 
50 void qjxg(lol r,lol z,lol y,lol zz,lol yy,lol v)
51 {
52 if (z>yy||y<zz) return;
53 if (z>=zz&&y<=yy) {
54 lazy[r]+=v;
55 sgm[r]+=(y-z+1)*v;
56 return;
57 }
58 if (lazy[r]) xia(r,z,y);
59 int k=z+y>>1;
60 if (z<=k) qjxg(ll(r),z,k,zz,yy,v);
61 if (y>k) qjxg(rr(r),k+1,y,zz,yy,v);
62 shang(r);
63 }
64 
65  
66 
67 lol cx(lol r,lol z,lol y,lol zz,lol yy)
68 {
69 if (z>yy||y<zz) return 0;
70 if (z>=zz&&y<=yy) return sgm[r];
71 int k=z+y>>1;
72 if (lazy[r]) xia(r,z,y);
73 return cx(ll(r),z,k,zz,yy)+cx(rr(r),k+1,y,zz,yy);
74 }
75 
76  
77 
78 int main()
79 {
80 cin>>n>>m;
81 for (int i=1;i<=n;i++) {
82 scanf("%lld",&a[i]);
83 }
84 js(1,1,n);
85 lol flag,x,y,k;
86 for (int i=1;i<=m;i++) {
87 scanf("%lld",&flag);
88 if (flag==1) {
89 scanf("%lld%lld%lld",&x,&y,&k);
90 qjxg(1,1,n,x,y,k);
91 }
92 else {
93 scanf("%lld%lld",&x,&y);
94 cout<<cx(1,1,n,x,y)<<endl;
95 }
96 }
97 return 0;
98 }

 

十二、

 SPFA

 1 //SPFA
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 using namespace std;
 7 
 8  
 9 
10 int n,m,st,d[10010];
11 
12  
13 
14 int cnt;
15 int o[500010];
16 int s[500010][3];
17 //lsqxx!!!
18 void jia(int x,int y,int c)
19 {
20 s[++cnt][1]=o[x];
21 s[cnt][0]=y;
22 s[cnt][2]=c;o[x]=cnt;
23 }
24 
25  
26 
27 queue <int> q;
28 bool v[10010];
29 
30  
31 
32 void SPFA()
33 {
34 for (int i=1;i<=n;i++)
35 d[i]=2147483647;
36 v[st]=1;q.push(st);d[st]=0;
37 while (!q.empty()) {
38 int x=q.front();
39 for (int i=o[x];i;i=s[i][1]) {
40 int y=s[i][0];
41 if (d[y]>d[x]+s[i][2]) {
42 d[y]=d[x]+s[i][2];
43 if (!v[y]) {
44 v[y]=1;
45 q.push(y);
46 }
47 }
48 }
49 q.pop();v[x]=0;
50 }
51 }
52 
53  
54 
55 int main()
56 {
57 int x,y,c;
58 cin>>n>>m>>st;
59 for (int i=1;i<=m;i++) {
60 scanf("%d%d%d",&x,&y,&c);
61 jia(x,y,c);
62 }
63 SPFA();
64 for (int i=1;i<=n;i++) {
65 printf("%d ",d[i]);
66 }
67 cout<<endl;
68 return 0;
69 }

 

 十三、

树链剖分

 1 //shupou
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #define ll(x) ((x)<<1)
 6 #define rr(x) ((x)<<1|1)
 7 using namespace std;
 8 typedef long long l;
 9 
10 const int N=100010;l n,m,r,p,cnt,dfscnt;
11 l d[N],id[N],f[N],son[N],top[N],siz[N],sgm[N*4],lazy[N*4],a[N],w[N],o[N],s[N*2][2];
12 
13 void jia(l x,l y) {s[++cnt][1]=o[x];s[cnt][0]=y;o[x]=cnt;}
14 
15 void dfs(l x,l fa,l dep)
16 {
17     f[x]=fa;d[x]=dep;siz[x]=1;l mm=-1;
18     for (int i=o[x];i;i=s[i][1]) {
19         if (s[i][0]!=fa) {
20             dfs(s[i][0],x,dep+1);siz[x]+=siz[s[i][0]];
21             if (siz[s[i][0]]>mm) son[x]=s[i][0],mm=siz[s[i][0]];
22         }
23     }
24 }
25 
26 void build(l x,l tp)
27 {
28     id[x]=++dfscnt;top[x]=tp;a[dfscnt]=w[x];
29     if (son[x]) build(son[x],tp);
30     for (int i=o[x];i;i=s[i][1])
31     if ((s[i][0]!=f[x])&&(son[x]!=s[i][0])) build(s[i][0],s[i][0]);
32 }
33 
34 void xia(l r,l z,l y)
35 {
36     l k=z+y>>1;lazy[ll(r)]+=lazy[r];lazy[rr(r)]+=lazy[r];
37     sgm[ll(r)]+=(k-z+1)*lazy[r];
38     sgm[rr(r)]+=(y-k)*lazy[r];
39     sgm[ll(r)]%=p;sgm[ll(r)]%=p;lazy[r]=0;
40 }
41 
42 void js(l r,l z,l y)
43 {
44     if (z==y) {sgm[r]=a[z];if (sgm[r]>p) sgm[r]%=p;return;}
45     l k=z+y>>1;js(ll(r),z,k);js(rr(r),k+1,y);sgm[r]=(sgm[ll(r)]+sgm[rr(r)])%p;
46 }
47 
48 void qjxg(l r,l z,l y,l zz,l yy,l v)
49 {
50     if (z>yy||y<zz) return;
51     if (z>=zz&&y<=yy) {
52         lazy[r]+=v;sgm[r]+=(y-z+1)*v;return;}
53     if (lazy[r]) xia(r,z,y);l k=z+y>>1;
54     if (z<=k) qjxg(ll(r),z,k,zz,yy,v);if (y>k) qjxg(rr(r),k+1,y,zz,yy,v);
55     sgm[r]=(sgm[ll(r)]+sgm[rr(r)])%p;
56 }
57 
58 l cx(l r,l z,l y,l zz,l yy)
59 {
60     if (z>yy||y<zz) return 0;
61     if (z>=zz&&y<=yy) return sgm[r]%p;
62     l k=z+y>>1;if (lazy[r]) xia(r,z,y);
63     return (cx(ll(r),z,k,zz,yy)+cx(rr(r),k+1,y,zz,yy))%p;
64 }
65 
66 l qiulu(l x,l y)
67 {
68     l ans=0;while (top[x]!=top[y]) {
69         if (d[top[x]]<d[top[y]]) swap(x,y);
70         ans+=cx(1,1,n,id[top[x]],id[x]);ans%=p;x=f[top[x]];
71     }
72     if (d[x]>d[y]) swap(x,y);ans+=cx(1,1,n,id[x],id[y]);ans%=p;
73     return ans;
74 }
75 
76 void jialu(l x,l y,l v)
77 {
78     v%=p;while (top[x]!=top[y]) {
79         if (d[top[x]]<d[top[y]]) swap(x,y);
80         qjxg(1,1,n,id[top[x]],id[x],v);x=f[top[x]];
81     }
82     if (d[x]>d[y]) swap(x,y);qjxg(1,1,n,id[x],id[y],v);
83 }
84 
85 int main()
86 {
87     l x,y,v,flag;cin>>n>>m>>r>>p;for (int i=1;i<=n;i++) scanf("%lld",&w[i]);
88     for (int i=1;i<n;i++) {scanf("%lld%lld",&x,&y);jia(x,y);jia(y,x);}dfs(r,0,1);build(r,r);js(1,1,n);
89     for (int i=1;i<=m;i++) {scanf("%lld",&flag);
90         if (flag==1) {scanf("%lld%lld%lld",&x,&y,&v);jialu(x,y,v);}
91         if (flag==2) {scanf("%lld%lld",&x,&y);printf("%lld\n",qiulu(x,y));}
92         if (flag==3) {scanf("%lld%lld",&x,&v);v%=p;qjxg(1,1,n,id[x],id[x]+siz[x]-1,v);}
93         if (flag==4) {scanf("%lld",&x);printf("%lld\n",cx(1,1,n,id[x],id[x]+siz[x]-1)%p);}
94     }
95     return 0;
96 }

 

 十四、

最小费用最大流

 1 //zxfyzdl
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 const int N=5010,M=100010,inf=2e9;
 8 int head,tail,cnt=-1,n,m,s,t,cost=0;
 9 int q[N*10],v[N],ss[M*2][4],o[N],d[N],vis[N];
10 
11 void jia(int a,int b,int c,int cc)
12 {
13     //ss[i][0]-->to;ss[i][1]-->next;ss[i][2]-->flow;ss[i][3]-->cost;
14     ss[++cnt][0]=b;ss[cnt][1]=o[a];
15     ss[cnt][2]=c;ss[cnt][3]=cc;o[a]=cnt;
16     ss[++cnt][0]=a;ss[cnt][1]=o[b];
17     ss[cnt][2]=0;ss[cnt][3]=-cc;o[b]=cnt;
18 }
19 
20 int dfs(int x,int flow)
21 {
22     v[x]=1;int rest=0;if (x==t) return flow;
23     for (int i=o[x];i!=-1;i=ss[i][1]) {
24         if ((d[ss[i][0]]==d[x]-ss[i][3])&&(v[ss[i][0]]==0)&&(ss[i][2]!=0)) {
25             int di=dfs(ss[i][0],min(flow-rest,ss[i][2]));
26             if (di>0) {rest+=di;ss[i][2]-=di;ss[i^1][2]+=di;}
27         }
28     }
29     return rest;
30 }
31 
32 bool spfa()
33 {
34     for (int i=1;i<=n;i++) d[i]=inf,vis[i]=0;
35     head=1;tail=2;q[1]=t;d[t]=0;vis[t]=1;
36     while (head!=tail) {
37         int u=q[head];
38         for (int i=o[u];i!=-1;i=ss[i][1]) {
39             if ((d[ss[i][0]]>d[u]-ss[i][3])&&(ss[i^1][2]!=0)) {
40                 d[ss[i][0]]=d[u]-ss[i][3];
41                 if (!vis[ss[i][0]]) {
42                     vis[ss[i][0]]=1;q[tail++]=ss[i][0];if (tail==n+1) tail=1;
43                 }
44             }
45         }
46         q[head++]=0;vis[u]=0;if (head==n+1) head=1;
47     }
48     return d[s]!=inf;
49 }
50 
51 void FU_DUI_SUAN_FA_BO_DA_JING_SHEN()
52 {
53     int ans=0,cntt=1;
54     while (spfa()) {
55         v[t]=1;
56         while (v[t]) {
57             memset(v,0,sizeof(v));
58             int l=dfs(s,inf);ans+=l;cost+=l*d[s];
59         }
60     }
61     cout<<ans<<" "<<cost<<endl;
62 }
63 
64 int main()
65 {
66     int a,b,c,cc;
67     memset(o,-1,sizeof(o));
68     cin>>n>>m>>s>>t;
69     for (int i=1;i<=m;i++) {
70         scanf("%d%d%d%d",&a,&b,&c,&cc);
71         jia(a,b,c,cc);
72     }
73     FU_DUI_SUAN_FA_BO_DA_JING_SHEN();
74     return 0;
75 }

 十五、

堆(手打)

 1 //heap-xiao
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 int n,flag,heap[1000010],heapsize;
 8 
 9 void jiaru(int d)
10 {
11     int now,next;heap[++heapsize]=d;now=heapsize;
12     while (now>1) {
13         next=now>>1;if (heap[now]>=heap[next]) break;
14         swap(heap[now],heap[next]);now=next;
15     }
16     return;
17 }
18 
19 int shanchu_quchu()
20 {
21     int now,next,res;res=heap[1];heap[1]=heap[heapsize--];now=1;
22     while (now*2<=heapsize) {
23         next=now*2;
24         if (next<heapsize&&heap[next+1]<heap[next]) next++;
25         if (heap[now]<=heap[next]) break;swap(heap[now],heap[next]);
26         now=next;
27     }
28     return res;
29 }
30 
31 int main()
32 {
33     cin>>n;int x;
34     while (n--) {
35         scanf("%d",&flag);
36         if (flag==1) {scanf("%d",&x);jiaru(x);}
37         if (flag==2) {printf("%d\n",heap[1]);}
38         if (flag==3) {int daiti=shanchu_quchu();}
39     }
40     return 0;
41 }

十六、

优先队列(STL)

 1 //priority_queue
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 int n,flag,a;
 9 priority_queue <int> heap;
10 
11 int main() {
12     cin>>n;
13     for (int i=1;i<=n;i++) {
14         cin>>flag;
15         if (flag==1) {
16             cin>>a;
17             heap.push(-a);
18         }
19         else if (flag==2) {
20             int f=heap.top();
21             cout<<-f<<endl;
22         }
23         else heap.pop();
24     }
25     return 0;
26 }

十七、

迪杰斯特拉(堆优化版本)

 1 //dijkstra-dyh
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #define MAXN 10010
 6 using namespace std;
 7 typedef pair<int,int>Pair;
 8 
 9 struct node {
10   int u,w,v,next;
11 }e[500010];
12 
13 int dis[MAXN],st[MAXN];
14 bool flag[MAXN];
15 int tot,start,n,m,x,y,z;
16 
17 void add(int x,int y,int z)
18 {
19   e[++tot].u=x;e[tot].v=y;
20   e[tot].w=z;
21   e[tot].next=st[x];st[x]=tot;
22 }
23 
24 int dijsktra(int start)
25 {
26   memset(dis,127,sizeof dis);
27   memset(flag,0,sizeof flag);
28   dis[start]=0;priority_queue< Pair,vector<Pair>,greater<Pair> >que;
29   que.push(make_pair(dis[start],start));
30   while (!que.empty()) {
31     Pair now=que.top();que.pop();
32     if (flag[now.second]) continue;
33     flag[now.second]=1;
34     for (int i=st[now.second];i;i=e[i].next)
35     if (dis[now.second]+e[i].w<dis[e[i].v]) {
36       dis[e[i].v]=dis[now.second]+e[i].w;
37       if (!flag[e[i].v]) que.push(make_pair(dis[e[i].v],e[i].v));
38     }
39   }
40   for (int i=1;i<=n;i++) {
41     if (dis[i]==2139062143) dis[i]=2147483647;
42     printf("%d ",dis[i]);
43   }
44 }
45 int main()
46 {
47   scanf("%d%d%d",&n,&m,&start);
48   for (int i=1;i<=m;i++) {
49     scanf("%d%d%d",&x,&y,&z);
50     add(x,y,z);
51   }
52   dijsktra(start);
53 }

十八、

迪杰斯特拉(线段树版本)

 1 //dijktra-xds
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm> 
 5 using namespace std;
 6 
 7 const int maxn =10007;
 8 const int maxm = 500007;
 9 const int INF = 0x7fffffff;
10 int n,m;
11 
12 inline int read()
13 {
14   int x=0;
15   char c=getchar();
16   while (c<0||c>9) c=getchar();
17   while (c>=0&&c<=9) x=x*10+c-0,c=getchar();
18   return x;
19 }
20 
21 struct node{
22   int v,next,w;
23 }edge[maxm];
24 
25 int num=0,head[maxn];
26 
27 inline void add_edge(int a,int b,int c) {
28   edge[++num].v=b;edge[num].w=c;edge[num].next=head[a];head[a]=num;
29 }
30 
31 int dis[maxn],ans[maxn],s,t;
32 int tree[maxn<<2],leaf;
33 
34 inline int check(int i,int j) {
35   return dis[i]<dis[j]?i:j;
36 }
37 
38 inline void build() {
39   std::memset(dis,0x3f,sizeof dis);
40   for (leaf=1;leaf<=n;leaf<<=1);--leaf;
41   for (int i=1;i<=n;++i)tree[leaf+i]=i;
42 }
43 
44 inline void modify(int x,int y) {
45   dis[x]=y,x+=leaf,x>>=1;
46   while(x) tree[x]=check(tree[x<<1],tree[x<<1|1]),x=x>>1;
47 }
48 
49 void dijkstra(int s) {
50   build();dis[s]=0;int u=s;
51   for (int i=1;i<=n;++i) {
52     ans[u]=dis[u];
53     const int disu=dis[u];
54     modify(u,INF); 
55     for (int j=head[u];j;j=edge[j].next){
56       int v=edge[j].v;
57       if (dis[v]<INF&&dis[v]>disu+edge[j].w)
58         modify(v,disu+edge[j].w);
59     }
60     u=tree[1];
61   }
62 }
63 
64 inline void put(int x)
65 {
66   if (x>9) put(x/10);
67   putchar(x%10+48);   
68 }
69 
70 int main() {
71     int k;
72     n=read(),m=read(),k=read();
73     for (int a,b,c,i=1;i<=m;++i) {
74         a=read(),b=read(),c=read();
75         add_edge(a,b,c);
76   }
77   dijkstra(k);
78   for (int i=1;i<=n;++i) {
79     if (dis[i]==0x3f3f3f3f) ans[i]=INF;
80       put(ans[i]);putchar( );
81   }
82   putchar(\n);
83   return 0;
84 }

 

未完待续。。。

从2017年暑假到现在手打的模板↑_↑

标签:turn   init   d+   cmp   push   typedef   for   jks   make   

原文:https://www.cnblogs.com/fushao2yyj/p/8067921.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号