Programming Contest Challenge Book

1.6二分法

 1 题目：有n张纸片，随机取4张（可放回），如4张面值加起来可等于m，则输出yes，否则no。纸片的面值为k[1],k[2]……
 2 
 3        思路：使用4次循环寻找会导致超时，所以假设4张分别为a,b,c,d，
 4 
 5 先计算二次循环a+b所有可能放入数组kk，然后将kk排序，
 6 
 7 最后使用二次循环（m-c-d）与kk用二分法比较，，最后确定是否有这个值。
 8 
 9 #include <stdio.h>
10 #include <algorithm>
11 using namespace std;
12 bool ss(int x);
13 void solve();
14     int n,m,r,k[500];
15     int kk[500];
16     bool f;
17 int main()
18 {
19     while(scanf("%d %d",&n,&m)!=EOF)
20     {
21         for(int i=0;i<n;i++)
22             scanf("%d",&k[i]);
23         solve();
24         if(f) printf("Yes
");
25         else printf("NO
");
26     }
27     return 0;
28 }
29 
30 void solve()
31 {
32     for(int a=0;a<n;a++)
33         for(int b=0;b<n;b++)
34         kk[a*n+b]=k[a]+k[b];
35          sort(kk,kk+n*n);
36           f=false;
37     for(int c=0;c<n;c++)
38         for(int d=0;d<n;d++)
39         if(ss(m-k[c]-k[d]))
40        {
41          f=true;
42        }
43 }
44 
45 bool ss(int x)
46 {
47     int l=0;r=n*n;
48     while(r-l>=1)
49     {
50         int i=(r+l)/2;
51         if(kk[i]>x)l=i+1;
52         else if (kk[i]==x) return true;
53         else r=i;
54     }
55 }
56 
57 
58 Tip:此题也可以使用检索a然后排序，然后（m-b-c-d）与a用二分法比较，套路差不多，但是第一种方法的思想明显比较高大上。
59 
60 对了，局部变量可以与全局变量重名，但是局部变量会屏蔽全局变量哦！！

1.6

2.1穷竭搜索

DFS

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 char ch[102][102];
 5 int xx[4]={0,1,0,-1};
 6 int yy[4]={1,0,-1,0};
 7 int H,W,cou;
 8 void DFS(int x, int y){
 9     int a=0;
10     char b=ch[x][y];
11     ch[x][y]='.';
12     for(int i = 0; i < 4; i++)
13     {
14         int xn = x + xx[i], yn = y + yy[i];
15         if(xn >= 0 && xn < W && yn >= 0 && yn < H && ch[xn][yn] == b)
16         {
17             DFS(xn, yn);
18         }
19     }
20     return ;
21 }
22 
23 int main()
24 {
25     while(cin >> W >> H&& (H && W))
26     {
27         cou = 0;
28         for(int i=0; i < W; i++)
29             for(int k=0; k < H; k++)
30             cin >> ch[i][k];
31         for(int i = 0; i < W; i++)
32                 for(int k = 0; k < H; k++)
33                     if(ch[i][k] != '.')
34                     {
35                         DFS(i, k);
36                         cou++;
37                     }
38         cout << cou << endl;
39     }
40     return 0;
41 }
42 
43 AOJ0118 CN

AOJ0118 CN

 1 #include <stdio.h>
 2 char ch[24][24];
 3 void solve(int H,int W);
 4 void find1(int H,int W);
 5 void dfs(int x,int y,int H,int W);
 6 int main()
 7 {
 8     int H,W,i;
 9     while(scanf("%d%d",&W,&H)!=EOF&&H!=0&&W!=0)
10     {
11         getchar();
12      for(i=0;i<H;i++)
13         gets(ch[i]);
14      find1(H,W);
15      solve(H,W);
16     }
17     return 0;
18 }
19 
20 void solve(int H,int W)//计数
21 {
22     int a=0;
23     for(int i=0;i<H;i++)
24         for(int k=0;k<W;k++)
25             if(ch[i][k]=='@')
26                 a++;
27      printf("%d
",a);
28 }
29 
30 void find1(int H,int W)//找到点
31 {
32     for(int i=0;i<H;i++)
33         for(int k=0;k<W;k++)
34             if(ch[i][k]=='@')
35                 {
36                     dfs(i,k,H,W);
37                     return;
38                 }
39 }
40 
41 void dfs(int x,int y,int H,int W)
42 {
43     int x1,y1,nx,ny;
44     ch[x][y]='@';
45     for(x1=-1;x1<=1;x1++)
46     {
47         nx=x+x1;
48             if(nx>=0&&nx<H&&ch[nx][y]!='#'&&ch[nx][y]!='@')
49                 dfs(nx,y,H,W);
50     }
51     for(y1=-1;y1<=1;y1++)
52     {
53         ny=y+y1;
54             if(ny>=0&&ny<W&&ch[x][ny]!='#'&&ch[x][ny]!='@')
55                 dfs(x,ny,H,W);
56     }
57     return;
58 }
59 
60 POJ1979

POJ1979

 1 #include <iostream>
 2 using namespace std;
 3 int ch[12],one,two,g,q;
 4 
 5 int DFS(int g){
 6 if(g == 10)
 7     {
 8         q=0;
 9         return 1;
10     }
11 else
12 {
13     for(int i = g; i < 10; i++){
14         for(int k = 1; k >= 0; k--)
15         {
16             if(q == 0) return 1;
17             if(k && ch[i] > one)
18                 {
19                     one = ch[i];
20                     DFS(i+1);
21                 }
22             else if(!k && ch[i] > two)
23                 {
24                     two = ch[i];
25                     DFS(i+1);
26                 }
27             else if(ch[i] < two &&ch[i] < one)
28                 {
29                     return 0;
30                 }
31         }
32     }
33 }
34 return 0;
35 }
36 int main()
37 {
38     int n;
39     cin >> n;
40     while(n--){
41      for(int i = 0; i < 10; i++)
42         cin >> ch[i];
43      one = ch[0];
44      two = 0;
45      q=1;
46      if(DFS(1)) cout << "YES" << endl;
47      else cout << "NO" << endl;
48     }
49     return 0;
50 }

AOJ0033 CN

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 int dx[4]={ 0, 1, -1, 0};
 6 int dy[4]={ 1, 0, 0, -1};
 7 int map1[22][22];
 8 int xn,yn,x1,y1,H,W,y2,x2,a;
 9 void dfs(int x1, int y1, int step){
10     if(step > 10) return ;
11     for(int i = 0; i < 4; i++){//四个方向
12         int xn = x1 + dx[i], yn = y1 + dy[i];
13         if(xn == x2 && yn == y2){
14             a=min(a, step + 1);
15             continue;
16         }
17         if(map1[xn][yn] == 1)continue;
18         while(xn >= 0 && xn < W && yn >= 0 && yn < H){
19                 xn += dx[i]; yn += dy[i];//继续往下面走
20             if(xn >= 0 && xn < W && yn >= 0 && yn < H)
21             {
22                 if(map1[xn][yn] == 0) continue;//直到撞墙或终点
23                 if(xn == x2 && yn == y2){//到达终点
24                     a= min(a, step + 1);
25                     return ;
26                 }
27                 map1[xn][yn] = 0;//停下来了，继续dfs，注意dfs前后面的墙。
28                 dfs(xn - dx[i], yn - dy[i], step + 1);
29                 map1[xn][yn] = 1;
30                 break;
31             }
32         }
33     }
34 return ;
35 }
36 
37 int main()
38 {
39     while(cin >> H >> W && H != 0 && W != 0){
40      for(int i = 0; i < W; i++)
41         for(int k = 0; k < H; k++){
42             cin >> map1[i][k];
43             if(map1[i][k] == 2){
44                 x1 = i; y1 = k;
45                 map1[i][k] = 0;
46             }
47             if(map1[i][k] == 3){
48                 x2 = i;
49                 y2 = k;
50                 map1[i][k] = 1;
51             }
52         }
53         a = 99;
54         dfs(x1, y1, 0);
55         if(a == 99 || a>10) cout << "-1" << endl;
56         else cout << a <<endl;
57     }
58     return 0;
59 }

POJ3009

BFS

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 int map1[305][305],step[305][305];
 6 typedef pair<int, int> P;
 7 struct stu{
 8 int x; int y; int t;
 9 };
10 struct stu ch[50002];
11 
12 int dx[5]={0, 1, 0, -1, 0};
13 int dy[5]={0, 0, 1, 0, -1};
14 
15 void zha(int M) {
16     memset(map1, -1, sizeof(map1));
17     for(int i = 0; i < M; i++)
18         for(int k = 0; k < 5; k++){//five points are burst.
19             int nx = ch[i].x + dx[k];
20             int ny = ch[i].y + dy[k];
21             if(nx >= 0 && nx < 303 && ny >= 0 && ny < 303 && (ch[i].t < map1[ny][nx] || map1[ny][nx] == -1))
22                 map1[ny][nx] = ch[i].t;//give everypoint the minimum burst time.
23         }
24 }
25 
26 int bfs() {
27 queue <P> que;
28 que.push( P (0, 0));
29 memset(step, -1, sizeof(step));
30 step[0][0]=0;
31 while(que.size()) {
32     P p= que.front();
33     que.pop();
34         if(map1[p.first][p.second] == -1){//find map1's -1 and print it
35             return step[p.first][p.second];
36         }
37     if(step[p.first][p.second] >= map1[p.first][p.second])continue;//the point had benn burst,so jump it
38     for(int i = 1; i < 5; i++) {//this is the point of four diretions that does not been destroy.
39         int nx = p.first + dx[i],ny = p.second + dy[i];
40         if(nx>=0 && ny >=0 &&step[nx][ny] == -1)//if it can arrive and does not exceed the map
41             {
42                  que.push(P(nx, ny));//push it to the queue and go
43                  step[nx][ny]=step[p.first][p.second]+1;//of course,step must add 1 when go.
44             }
45     }
46 }
47 return -1;
48 }
49 
50 int main()
51 {
52     int M,a;
53     while(~scanf("%d",&M))
54     {
55          for(int i=0; i<M; i++)
56             scanf("%d%d%d",&ch[i].x,&ch[i].y,&ch[i].t);
57          zha(M);
58          a=bfs();
59          printf("%d
",a);
60     }
61     return 0;
62 }

POJ3669

 1 #include <iostream>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 typedef pair<int, int> P;
 6 int sx,sy,H,W,N;
 7 char map1[1002][1002];
 8 int step[1002][1002];
 9 int dx[4] = {1,0,-1,0};
10 int dy[4] = {0,1,0,-1};
11 void find1(int g){
12 for(int i = 0; i < W; i++)
13     for(int k = 0; k < H; k++)
14         if(map1[i][k] == 'S' || map1[i][k] == (g+48)){
15         if(map1[i][k] == 'S') map1[i][k] ='.';
16         sx = i; sy = k;
17         return ;
18     }
19 }
20 
21 int bfs(int n)
22 {
23     memset(step,-1,sizeof(step));
24     queue <P> que;
25     que.push(P (sx,sy));
26     step[sx][sy] = 0;
27     while(que.size()){
28         int x = que.front().first, y = que.front().second;
29         que.pop();
30         for(int i = 0; i < 4; i++){
31             int xn = x + dx[i], yn = y + dy[i];
32             if(xn >= 0 && xn < W && yn >= 0 && yn < H && map1[xn][yn] != 'X' && step[xn][yn] == -1)
33                 {
34                     step[xn][yn] = step[x][y] + 1;
35                     if(map1[xn][yn] == (n+48))
36                         {
37                             return step[xn][yn];
38                         }
39                     que.push(P(xn, yn));
40                 }
41         }
42     }
43 return 0;
44 }
45 
46 int main()
47 {
48     cin >> W >> H >> N;
49     for(int i = 0; i < W; i++)
50         for(int k = 0; k < H; k++)
51         cin >> map1[i][k];
52     int step = 0;
53     find1(0);
54     step += bfs(1);
55     for(int i = 1; i < N; i++)
56     {
57 
58         find1(i);
59         step += bfs(i+1);
60     }
61     cout << step << endl;
62     return 0;
63 }

AOJ0558 CN

 1 #include <iostream>
 2 #include <queue>
 3 #include <string.h>
 4 #include <map>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int d[4]={ 1, -1, 4, -4};
 9 map<string, int> dp;
10 
11 void bfs(){
12 queue<string> que;
13 que.push("01234567");
14 dp["01234567"] = 0;
15 while(que.size()){
16     string now =que.front();
17     que.pop();
18     int p=0;
19     for(int j = 0; j < 8; j++)
20         if(now[j] == '0'){
21             p=j;
22             break;
23         }
24     for(int i = 0; i < 4; i++){
25         int pn= p + d[i];
26         if(pn >= 0 && pn < 8 && !(p == 3 && i == 0)
27          && !(p ==4 && i == 1)){
28             string next = now;
29             swap(next[p],next[pn]);
30             if(dp.find(next) == dp.end()){
31                 dp[next] = dp[now] + 1;
32                 que.push(next);
33                 }
34             }
35         }
36     }
37 return ;
38 }
39 
40 int main()
41 {
42     string line;
43     bfs();
44     while(getline(cin,line))
45     {
46      line.erase(remove(line.begin(), line.end(), ' '), line.end());
47      cout << dp[line] << endl;
48     }
49     return 0;
50 }

AOJ0121 CN

Search

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 int N,ch[12],sh[12],g,i,cou;
 7 bool judge[12];
 8 
 9 void solve(int a){
10     int leng=0,b=0;
11     for(int k = 0;k < i; k++)
12         if(!judge[k]){//如果没被访问过，就加入数组sh和b
13             sh[leng++] = ch[k];
14             b=b * 10 + ch[k];
15         }
16     if(sh[0] != 0 || leng == 1)
17         cou = min(cou,abs(a-b));
18     while(next_permutation(sh,sh+leng)){//（除了原数组）全排列的所有情况
19         b=0;
20         for(int k = 0; k < leng; k++)
21             b = b * 10 + sh[k];
22         if(sh[0] != 0 || leng == 1)
23             {
24                 cou = min(cou,abs(a-b));
25             }
26     }
27 return ;
28 }
29 
30 void dfs(int x, int y){
31     if(x == i/2){
32         solve(y);
33         return;
34     }
35     for(int k=0; k < i; k++){
36         if(!judge[k]){
37             if(ch[k] == 0 && x == 0 && i > 3)
38                 continue;
39             judge[k]=true;//被访问过
40             dfs(x + 1, y * 10 + ch[k]);
41             judge[k]=false;
42         }
43     }
44     return ;
45 }
46 
47 
48 int main()
49 {
50     cin >> N;
51     getchar();
52     while(N--){
53         for( i = 0;;){
54                 cin>> ch[i++];
55                 if(g=getchar() == '
')
56                     break;
57             }
58         cou=1000000;
59         memset(judge,false,sizeof(judge));
60         dfs(0,0);
61         cout << cou <<endl;
62     }
63     return 0;
64 }

POJ2718

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int n,sum;
 5 int tri[10][10];
 6 
 7 int main()
 8 {
 9     while(cin >> n >> sum)
10     {
11         int lie[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
12         do{
13                 for(int k = 0; k < n; k++)
14                     tri[0][k]=lie[k];//first line
15                 for(int i = 1; i < n; i++)
16                     for(int g = 0 ; g < n - i; g++)//next line
17                     tri[i][g] = tri[i-1][g] + tri[i-1][g+1];
18                 if(tri[n-1][0] == sum )
19                     break;
20         } while(next_permutation(lie, lie+n));
21 
22         for(int j = 0; j < n ; j++){
23             if(j != 0)
24                 cout << " ";
25             cout << lie[j];
26         }
27         cout << endl;
28     }
29     return 0;
30 }

POJ3187

 1 #include <iostream>
 2 using namespace std;
 3 int map1[5][5],cou[10000000];
 4 int a,n,h;
 5 int x1[4] = {0, 1, -1, 0};
 6 int y1[4] = {1, 0, 0, -1};
 7 
 8 void dfs(int x, int y, int c, int all){
 9 if(c == 6)
10     {
11         cou[n++] = all;
12         for(h = 0; h < n-1; h++)
13             if(all == cou[h])
14             break;
15         if(h == n-1)
16                 a++;
17         return ;
18     }
19 for(int i = 0; i < 4; i++)
20     {
21         int xn = x + x1[i], yn = y + y1[i];
22         if(xn >= 0 && xn <= 4 && yn >= 0 && yn <= 4)
23             {
24             dfs(xn, yn, c + 1, all * 10 + map1[xn][yn]);
25             }
26     }
27 return ;
28 }
29 
30 int main()
31 {
32     a = 0;
33     n = 0;
34     for(int i = 0; i < 5; i++)
35         for(int k = 0; k < 5; k++)
36         cin >> map1[i][k];
37     for(int i = 0; i < 5; i++)
38         for(int k = 0; k < 5; k++)
39         dfs(i, k, 1, map1[i][k]);
40     cout << a << endl;
41     return 0;
42 }

POJ3050

 1 #include <iostream>
 2 #include <bitset>
 3 using namespace std;
 4 
 5 bitset<10000> map1[10];
 6 int r,c,cou;
 7 
 8 void dfs(int all){
 9     if(all == r)
10         {
11             int num, upcou=0;
12             for(int i = 0; i < c; i++)
13                 {
14                     num=0;
15                     for(int k = 0; k < r; k++)//竖向翻转取大的
16                     if(map1[k][i])
17                     num++;
18                     upcou += max(num, r-num);
19                 }
20             cou = max(cou, upcou);
21             return;
22         }
23     dfs(all+1);//所有情况
24     map1[all].flip();
25     dfs(all+1);
26     return ;
27 }
28 int main()
29 {
30     while(cin >> r >> c)//r行c列
31     {
32         if(r == 0 && c == 0)
33             break;
34      for(int i = 0,g; i < r; i++)
35         for(int k = 0; k < c; k++)
36             {
37             cin >> g;
38             map1[i][k]=g;
39             }
40         cou = 0;
41         dfs(0);
42         cout << cou <<endl;
43     }
44     return 0;
45 }

AOJ0525 CN

2.2 贪心

区间

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 25000;
 6 pair<int, int> line[maxn];
 7 int g,h,N,T,j,maxitime;
 8 
 9 int main()
10 {
11      int i, t, cou = 0;
12      cin >> N >> T;
13      for(i = 0; i < N; i++)
14         cin >> line[i].first >> line[i].second;
15      sort(line, line + N);//排序，按照开始时间>>结束时间
16 
17      if(line[0].first != 1) printf("-1
");//不是从1开始则失败
18      else
19         {
20             t=line[0].second;
21             i = 1;
22             while(line[i].first == 1) t = line[i++].second;//取得第一段结束时间最晚的
23             cou = 1;
24 
25             while(t < T)//后面的段
26             {
27                 if(i >= N)break;
28                 j = i;
29                 maxitime=line[i].second;
30                 i++;
31                 while( i < N && line[i].first <= t+1)//往后取，直到取尽或者不连续
32                 {
33                     if(line[i].second > maxitime)
34                         {
35                             maxitime=line[i].second;//取得每一段结束时间最晚的
36                             j=i;//j是有效的段
37                         }
38                     i++;//往后取
39                 }
40                 if(maxitime <= t || line[j].first > t+1) break;//不能取完或是非正常区域内的段
41                 else
42                     {
43                      cou++;
44                      t = line[j].second;//更新结束时间
45                     }
46             }
47             if(t<T) printf("-1
");
48             else printf("%d
",cou);
49         }
50     return 0;
51 }

POJ2376

 1 #include <iostream>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 bool flag;
 7 int ans,T = 0,head,tail,n,d,a,b;
 8 
 9 struct point{
10     double x,y;
11     point(double a = 0, double b = 0){ x = a, y = b; }
12     bool operator < (const point c)const {return x < c.x;}
13 }queue1[1005];
14 
15 void push(point v){queue1[tail++]=v;}
16 void pop(){head++;}
17 
18 bool judge(point &t,point v){
19 if(!( t.x>v.y || t.y< v.x))
20     {
21      t.x = min(t.x,v.x);
22      t.y = min(t.y,v.y);
23      return true;
24     }
25 return false;
26 }
27 
28 int main()
29 {
30     while(cin >> n >> d)
31     {
32         if(!n && !d) break;
33         ans = flag = head = tail = 0;
34             for(int i = 0; i < n; i++)
35         {
36             cin >> a >> b;
37             if(b > d) flag = 1;
38             else
39             {
40                 push(point(a-sqrt((double)d*d - b*b),a+sqrt((double)d*d - b*b)));
41             }
42         }
43         if(flag) cout << "Case " << ++T << ": " << "-1" <<endl;
44         else
45         {
46             sort(queue1, queue1 + n);
47             while(head != tail)
48             {
49                 ans++;
50                 point t = queue1[head];
51                 while(head != tail)
52                 {
53                     point v = queue1[head];
54                     if(judge(t,v)) pop();
55                     else break;
56                 }
57             }
58             cout << "Case " << ++T << ": " << ans <<endl;
59         }
60     }
61     return 0;
62 }

POJ1328

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int N,house[50005];
 7 
 8 struct stu{
 9     int a,b,site;
10 
11     bool operator < (const stu &a1) const {
12     if(b == a1.b) return a > a1.a;
13     else return b > a1.b;
14     }
15 } line[50005];
16 
17 priority_queue<stu> que;
18 
19 bool cmp(stu a1, stu b1){
20     if(a1.a > b1.a) return false;
21     if(a1.a < b1.a) return true;
22     else return a1.b < b1.b;
23 }
24 
25 
26 int main()
27 {
28     while(cin >> N)
29         {
30             for(int i = 0; i < N; i++)
31                 {
32                     cin >> line[i].a >> line[i].b;
33                     line[i].site = i;
34                 }
35         sort(line, line + N, cmp);
36 
37         int cou=1;
38         house[line[0].site] = 1;
39         que.push(line[0]);
40         for(int i = 1; i < N; i++)
41             {
42              if(!que.empty() && que.top().b < line[i].a)
43              {
44                  house[line[i].site] = house[que.top().site];
45                  que.pop();
46              }
47              else
48              {
49                  cou++;
50                  house[line[i].site] = cou;
51              }
52              que.push(line[i]);
53             }
54 
55             cout << cou <<endl;
56             for(int i = 0; i < N; i++)
57                 cout << house[i] <<endl;
58             while(!que.empty())
59                 que.pop();
60         }
61     return 0;
62 }

POJ3190

其他

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int ch[10010][2];
 5 
 6 int main()
 7 {
 8     int n, s;
 9     cin >> n >> s;
10     int maxi = 0, mini = 0;
11     for(int i = 0; i < n; i++)
12     {
13         cin >> ch[i][0] >> ch[i][1];
14         maxi = max(maxi, ch[i][0]);
15         mini = min(mini, ch[i][0]);
16     }
17     maxi = (maxi-mini)/s;
18     long long ans = 0, cou;
19     for(int i = 0; i < n; i++)
20     {
21         int cou = ch[i][0] * ch[i][1];
22         for(int k = i-1; k >= 0; k--)
23         {
24             if(i-k>maxi)break;//再往前找没有意义，不然tle
25             if(cou > ch[k][0] * ch[i][1] + (i-k)*ch[i][1]*s)
26             cou = ch[k][0] * ch[i][1] + (i-k)*ch[i][1]*s;
27         }
28         ans += cou;
29     }
30     cout << ans << endl;
31     return 0;
32 }
33 
34 //下面O(n)
35 
36 #include <iostream>
37 using namespace std;
38 
39 int ch[10010][2];
40 
41 int main()
42 {
43     int n, s;
44     cin >> n >> s;
45     for(int i = 0; i < n; i++)
46         cin >> ch[i][0] >> ch[i][1];
47 
48     long long ans = 0, cou = 0x3f3f3f3f;
49     for(int i = 0; i < n; i++)
50     { //cou是从0-i花费的最小值，不断更新
51         cou+=s;
52         if(cou > ch[i][0]) cou = ch[i][0];
53         ans += cou*ch[i][1];
54     }
55     cout << ans << endl;
56     return 0;
57 }

POJ2393

2.3 DP

简单dp

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n, dp[355][355], ch[355][355];
 8     cin >> n;
 9     memset(dp,0,sizeof(dp));
10     for(int i = 0; i < n; i++)
11         for(int j = 0; j <= i; j++)
12             cin >> ch[i][j];
13     for(int i = 0; i < n; i++)
14         dp[n-1][i] = ch[n-1][i];
15     for(int i = n-2; i >= 0; i--)
16         for(int k = 0; k <= i; k++)
17         dp[i][k] = ch[i][k] + max(dp[i+1][k], dp[i+1][k+1]);
18     cout << dp[0][0] <<endl;
19     return 0;
20 }

POJ3176

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int dp[1000010];
 5 
 6 int main()
 7 {
 8     int n;
 9     cin >> n;
10     dp[1] = 1;
11     for(int i = 2; i <= n; i++)
12     {
13         if(i & 1)
14             dp[i] = dp[i-1];
15         else
16             dp[i] = (dp[i-1] + dp[i/2])%1000000000;
17     }
18     cout << dp[n] << endl;
19     return 0;
20 }

POJ2229

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int ch[1010],dp[1010][32];
 6 
 7 int main()
 8 {
 9     int n,m;
10     cin >> n >>m;
11     for(int i = 1; i <= n; i++)
12         cin >> ch[i];
13     memset(dp,0,sizeof(dp));
14     if(ch[1] == 1) dp[1][0] = 1;
15     dp[1][1] = 1;
16     for(int i = 1; i <= n; i++)
17         for(int k = 0; k <= m; k++)
18         {
19             if(k == 0)
20             {
21                 dp[i][k] = dp[i-1][k] + ch[i]%2;
22                 continue;
23             }
24             dp[i][k] = max(dp[i][k], dp[i-1][k]+(k%2+1 == ch[i]));//k是偶数且树1掉  || k是奇数且树2掉   不走，捡
25             dp[i][k] = max(dp[i][k], dp[i-1][k-1]+(k%2 == ch[i]));//树1掉 k-1是奇数 不走不捡
26             dp[i][k] = max(dp[i][k], dp[i-1][k-1]+(k%2+1 == ch[i]));//树1掉 k是偶数 走，捡 || 树2掉 k-1是偶数 不走不捡
27                                                                     //树2掉 k是奇数 走，捡
28         }
29     cout << dp[n][m] <<endl;
30     return 0;
31 }

POJ2385

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int t[1010],n,m,r;
 6 
 7 struct st{
 8     int from, to, cost;
 9 }ch[1010];
10 //t[i]表示在ch[i].to之后的最大挤奶量
11 //t[i] = max(t[i], t[k]+(第i次挤奶.cost));
12 void solve(){
13     for(int i = 0; i < m; i++)
14     {
15         t[i] = ch[i].cost;
16         for(int k = 0; k < i; k++)
17         {
18             if(ch[k].to <= ch[i].from)
19                 t[i] = max(t[i], t[k]+ch[i].cost);
20         }
21     }
22     return;
23 }
24 
25 int cmp(st a, st b){
26     return a.from < b.from;
27 }
28 
29 
30 int main()
31 {
32     cin >> n >> m >> r;
33     for(int i = 0; i < m; i++)
34     {
35         int a,b,c;
36         cin >> a >> b >> c;
37         ch[i].from = a;
38         ch[i].to = b + r;
39         ch[i].cost = c;
40     }
41     sort(ch,ch+m,cmp);//按照开始时间，早的在前
42     solve();
43     int ans = t[0];
44     for(int i = 0; i < m; i++)
45         ans = max(ans,t[i]);
46     cout << ans <<endl;
47     return 0;
48 }

POJ3616

 1 #include <iostream>
 2 #include <math.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 int dp[2020][2020];
 7 char ch[2020];
 8 int cost[200];
 9 
10 int main()
11 {
12     int n,m;
13     cin >> n >> m;
14     cin >> ch;
15     for(int i = 0; i < n; i++)
16     {
17         char a;
18         int b,c;
19         cin >> a >> b >> c;
20         cost[a] = min(b, c);//假设为abcd变成d和变成abcdcba都是回文串，所以花费取最小值就ok
21     }
22     memset(dp,0,sizeof(dp));
23     for(int i = m-1; i >= 0; i--)
24         for(int k = i+1; k < m; k++)
25         {
26             dp[i][k] = min(dp[i+1][k] + cost[ch[i]], dp[i][k-1] + cost[ch[k]]);//现在状态=上个状态加头||上个状态加尾
27             if(ch[i] == ch[k])//头尾相同=去头尾
28                 dp[i][k] = min(dp[i][k], dp[i+1][k-1]);
29         }
30     cout << dp[0][m-1]<<endl;
31     return 0;
32 }

POJ3280

2.5 图

最短路

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 #define INF 0x3f3f3f3f
 6 #define MAX 10010
 7 using namespace std;
 8 
 9 int V,m,k;
10 int cost[MAX][MAX];
11 int d[MAX];
12 bool used[MAX];
13 
14 void dijkstra(){
15     fill(d, d+V+1, INF);
16     fill(used, used+V+1, false);
17     d[1] = 0;
18     while(true)
19     {
20         int v = -1;
21         for(int u = 1; u <= V; u++)
22         {
23             if(!used[u] && (v == -1 || d[u] < d[v]))
24                 v = u;
25         }
26         if(v == -1) break;
27         used[v] = true;
28         for(int i = 1; i <= V; i++)
29             d[i] = min(d[i], d[v] + cost[v][i]);
30     }
31 }
32 
33 
34 int main()
35 {
36     while(~scanf("%d%d",&V,&m))
37     {
38         if(!V&&!m) break;
39         for(int i = 0; i <= V; i++)
40             for(int k = 0; k <=V; k++)
41             {
42                 cost[i][k] = INF;
43                 if(i==k)
44                     cost[i][k] = 0;
45             }
46         int x, y, l;
47         for(int i = 0; i < m; i++)
48         {
49             scanf("%d%d%d",&x,&y,&l);
50             cost[y][x] = cost[x][y] = min(cost[x][y], l);
51         }
52         dijkstra();
53         printf("%d
",d[V]);
54         //for(int i = 1; i<=V;i++)//test
55         //    printf("now --%d %d
", i, d[i]);
56 
57     }
58     return 0;
59 }

HDU2544

  1 #include <iostream>
  2 #include <string.h>
  3 using namespace std;
  4 
  5 struct edge{
  6     int from, to, cost;
  7 }ed[5250];
  8 
  9 int n,m,w,d[509];
 10 
 11 bool find_negative_loop(){
 12     memset(d,0,sizeof(d));
 13 
 14     for(int i = 0; i < n; i++)
 15     {
 16         for(int j = 0; j < m+w+m; j++)
 17         {
 18             edge e = ed[j];
 19             if(d[e.to] > d[e.from] + e.cost)
 20             {
 21                 d[e.to] = d[e.from] + e.cost;
 22 
 23                 if(i == n-1)
 24                     return true;
 25             }
 26         }
 27     }
 28     return false;
 29 }
 30 
 31 int main()
 32 {
 33     int f;
 34     cin >> f;
 35     while(f--)
 36     {
 37         int i,s,e,t;
 38         cin >> n >> m >> w;
 39         for(i = 0; i < m; i++)
 40         {
 41              cin >> s >> e >> t;
 42              ed[i].from = s;
 43              ed[i].to = e;
 44              ed[i].cost = t;
 45         }
 46         for(; i < m+w; i++)
 47         {
 48              cin >> s >> e >> t;
 49              ed[i].from = s;
 50              ed[i].to = e;
 51              ed[i].cost = -t;
 52         }
 53         for(; i < m+w+m; i++)
 54         {
 55              ed[i].from = ed[i-m-w].to;
 56              ed[i].to = ed[i-m-w].from;
 57              ed[i].cost = ed[i-m-w].cost;
 58         }
 59         if(find_negative_loop())
 60             cout << "YES" << endl;
 61         else cout << "NO" << endl;
 62     }
 63     return 0;
 64 }
 65 
 66 
 67 
 68 #include <iostream>
 69 using namespace std;
 70 
 71 int n,w,m,d[520],num,s,e,t;
 72 struct edge{
 73     int from, to, cost;
 74 }eg[5203];
 75 
 76 bool shortpath(){
 77     bool flag;
 78     d[1] = 0;
 79     for(int i = 1; i < n; i++)
 80     {
 81         flag = false;
 82         for(int j = 0; j < num; j++)
 83             if(d[eg[j].from] + eg[j].cost < d[eg[j].to])
 84             {
 85                 d[eg[j].to] = d[eg[j].from] + eg[j].cost;
 86                 flag = true;
 87             }
 88         if(!flag)
 89             return false;
 90     }
 91     for(int i = 0; i < num; i++)
 92         if(d[eg[i].from] + eg[i].cost < d[eg[i].to])
 93         return true;
 94 
 95 }
 96 
 97 int main()
 98 {
 99     int T;
100     cin >> T;
101         while(T--)
102     {
103         num = 0;
104         cin >> n >> m >> w;
105         for(int i = 0; i < m; i++)
106         {
107             cin >> s >> e >> t;
108             eg[num].from = s;
109             eg[num].to = e;
110             eg[num++].cost = t;
111             eg[num].from = e;
112             eg[num].to = s;
113             eg[num++].cost = t;
114         }
115         for(int i = 0; i < w; i++)
116         {
117             cin >> s >> e >> t;
118             eg[num].from = s;
119             eg[num].to = e;
120             eg[num++].cost = -t;
121         }
122         for(int i = 1; i <= n; i++)
123             d[i]=0x3f3f3f3f;
124         if(shortpath())
125             cout << "YES" <<endl;
126         else cout << "NO" << endl;
127     }
128     return 0;
129 }
130 
131 POJ3259

POJ3259

 1 #include <iostream>
 2 #include <queue>
 3 #include <functional>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 struct edge{
 8     int v, d, c;
 9     edge(){}
10     edge(int v, int d, int c) : v(v),d(d),c(c){}
11 };
12 
13 int N, M;
14 const int INF = 0x3f3f3f3f;
15 typedef pair<int, int> P;//距离， 终点
16 int d[10665];
17 
18 vector<edge> G[10665];
19 
20 void dijkstra(int s){
21     priority_queue<P, vector<P>, greater<P> > que;
22     memset(d, INF, sizeof(d));
23     d[s] = 0;
24     que.push(P(0,s));
25     while(!que.empty())
26     {
27         P p = que.top();
28         que.pop();
29         int q = p.second;
30         if(d[q] < p.first) continue;//不是最短
31         for(int i = 0; i < G[q].size(); i++)
32         {
33             edge e = G[q][i];
34             if(d[e.v] > d[q] + e.d)// 更新
35             {
36                 d[e.v] = d[q] + e.d;
37                 que.push(P(d[e.v], e.v));
38             }
39         }
40     }
41 }
42 
43 
44 int main()
45 {
46     while(cin >> N >> M)
47     {
48         if(!N) break;
49         for(int i = 0; i < N; i++)
50         {
51             G[i].clear();
52         }
53         for(int i = 0; i < M; i++)
54         {
55             int u,t,c,d;
56             cin >> u >> t >> d >> c;
57             u--;t--;
58             G[u].push_back(edge(t,d,c));
59             G[t].push_back(edge(u,d,c));
60         }
61         dijkstra(0);
62         int ans=0;
63         for(int k = 1; k < N; k++)
64         {
65             int mincost = INF;
66             for(int j = 0; j < G[k].size(); j++)
67             {
68                 if(d[G[k][j].v]+G[k][j].d == d[k]
69                      && G[k][j].c < mincost)
70                     mincost = G[k][j].c;
71             }
72             ans += mincost;
73         }
74         cout << ans << endl;
75     }
76     return 0;
77 }
78 
79 AOJ2249

AOJ2249

 1 #include <iostream>
 2 #include <string.h>
 3 #include <math.h>
 4 using namespace std;
 5 
 6 int d[10][10];
 7 
 8 void floyd(int m){
 9     for(int i = 0; i < m; i++)
10         for(int k = 0; k < m; k++)
11             for(int j = 0; j < m; j++)
12                 d[k][j] = min(d[k][j], d[k][i] + d[i][j]);
13 }
14 
15 void init(int m)
16 {
17     for(int i = 0; i < m; i++)
18     {
19         for(int j = 0; j < i; j++)
20         {
21             d[i][j] = d[j][i] = 0x3f3f3f3f;
22         }
23         d[i][i]=0;
24     }
25 }
26 
27 int main()
28 {
29     int T, x, y, s, m;
30     while(cin >> T && T)
31     {
32         init(10);
33         m = 0;
34         for(int i = 0; i < T; i++)
35         {
36             cin >> x >> y >> s;
37             d[y][x] = d[x][y] = min(d[x][y], s);
38             m = max(max(m,x), y);
39         }
40         floyd(m+1);
41         int ans = 0x3f3f3f3f, point = 0;
42         for(int i = 0; i <= m; i++)
43         {
44             int cou = 0;
45             for(int k = 0; k <= m; k++)
46                 if(d[i][k] != 0x3f3f3f3f)
47                     cou+=d[i][k];
48             if(cou < ans)
49             {
50                 ans = cou;
51                 point = i;
52             }
53         }
54         cout << point << " " << ans << endl;
55 
56     }
57     return 0;
58 }
59 
60 AOJ0189 CN

AOJ0189 CN

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 int d[305][305], n, ch[10010];
 6 
 7 void floyd(){
 8     for(int i = 0; i < n; i++)
 9         for(int k = 0; k < n; k++)
10             for(int j = 0; j < n; j++)
11                 d[k][j] = min(d[k][j], d[k][i] + d[i][j]);
12 }
13 
14 int main()
15 {
16     int m, t;
17     cin >> n >> m;
18     memset(d, 0x3f3f3f3f, sizeof(d));
19     for (int i = 0; i < n; i++)
20             d[i][i] = 0;
21     while(m--)
22     {
23         cin >> t;
24         for(int i = 0; i < t; i++)
25         {
26             cin >> ch[i];
27             ch[i]--;
28         }
29 
30     for(int i = 0; i < t; i++)
31         for(int j = i + 1; j < t; j++)
32         {
33             d[ch[i]][ch[j]] = d[ch[j]][ch[i]] = 1;
34         }
35     }
36     floyd();
37     int ans = 0x3f3f3f3f;
38     for(int i = 0; i < n; i++)
39         {
40             int cou = 0;
41             for(int j = 0; j < n; j++)
42             {
43                 cou += d[i][j];
44             }
45             ans = min(ans, cou);
46         }
47         int a = ans * 100 / (n-1);
48     cout << a << endl;
49     return 0;
50 }
51 
52 POJ2139

POJ2139

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <string.h>
 5 using namespace std;
 6 #define Max 1028
 7 
 8 int n, m, p;
 9 
10 struct edge{
11     int to,cost;
12     edge(){}
13     edge(int to, int cost) : to(to), cost(cost){}
14 };
15 
16 int d[Max][Max];
17 
18 typedef pair<int, int> P;
19 
20 vector<edge> g[Max];
21 
22 void dijkstra(int s){
23     priority_queue<P, vector<P>, greater<P> > que;
24     memset(d[s], 0x3f3f, Max * sizeof(int));
25     d[s][s] = 0;
26     que.push(P(0, s));
27 
28     while(que.size())
29     {
30         P p = que.top(); que.pop();
31         int v = p.second;
32         if(d[s][v] < p.first) continue;
33         for(int i = 0; i < g[v].size(); i++)
34         {
35             edge e = g[v][i];
36             if(d[s][e.to] > d[s][v] + e.cost)
37             {
38                 d[s][e.to] = d[s][v] + e.cost;
39                 que.push(P(d[s][e.to], e.to));
40             }
41         }
42     }
43     return ;
44 }
45 
46 
47 int main()
48 {
49     cin >> n >> m >> p;
50     p--;
51     int a, b, c;
52     for(int i = 0; i < m; i++)
53     {
54         cin >> a >> b >> c;
55          --a;
56          --b;
57         g[a].push_back(edge(b,c));
58     }
59     for(int i = 0; i < n; i++)
60         dijkstra(i);
61 
62     int ans = 0;
63     for(int i = 0; i < n; i++)
64     {
65         if(i == p)
66             continue;
67         ans = max(ans, d[i][p] + d[p][i]);
68     }
69     cout << ans <<endl;
70     return 0;
71 }
72 
73 POJ3268

POJ3268

 1 #include<iostream>
 2 #include<algorithm>
 3 #define Maxn 205
 4 #define Maxt 1024
 5 #define INF 1e8
 6 using namespace std;
 7 
 8 int n, m;
 9 int ch[Maxt];
10 int dl[Maxn][Maxn],ds[Maxn][Maxn];
11 int dp[Maxt][Maxn];
12 
13 int main()
14 {
15     while(cin >> n >> m && (n||m))
16     {
17         for(int i = 0; i < n; i++)//initialize
18             for(int k = 0; k < n; k++)
19             {
20                 if(i == k)
21                 {
22                     dl[i][k] = ds[i][k] = 0;
23                 }
24                 else
25                 {
26                     dl[i][k] = ds[i][k] = INF;
27                 }
28             }
29         for(int i = 0; i < m; i++)
30         {
31             int a, b, c;
32             char d;
33             cin >> a >> b >> c >> d;
34             a--;b--;
35             if(d == 'L')
36                 dl[b][a] = dl[a][b] = min(dl[a][b], c);
37             else
38                 ds[b][a] = ds[a][b] = min(ds[a][b], c);
39         }
40         int r;
41         cin >> r;
42         for(int i = 0; i < r; i++)
43         {
44             cin >> ch[i];
45             ch[i]--;
46         }
47 
48         for(int i = 0; i < n; i++)//floyd
49             for(int k = 0; k < n; k++)
50                 for(int j = 0; j < n; j++)
51                 {
52                     dl[k][j] = min(dl[k][j], dl[k][i]+dl[i][j]);
53                     ds[k][j] = min(ds[k][j], ds[k][i]+ds[i][j]);
54                 }
55         //---------------------------dp
56         for(int i = 0; i < r; i++)
57             for(int k = 0; k < n; k++)
58             {
59                 dp[i][k] = INF;
60             }
61         for(int i = 0; i < n; i++)
62             //到达第一个镇子之后，水路去其他镇子，再走路回来，那么船就丢在了i处
63             dp[0][i] = ds[ch[0]][i] + dl[i][ch[0]];
64         for(int i = 1; i < r; i++)//floyd
65             for(int k = 0; k < n; k++)
66                 for(int j = 0; j < n; j++)///会把船丢在j处
67                 {
68                     if(k != j)///                   i-1站   + 从i-1站走旱路去k+ 从k走水路去j+从j走旱路去i
69                         dp[i][j] = min(dp[i][j], dp[i-1][k] + dl[ch[i-1]][k] + ds[k][j]+ dl[j][ch[i]]);
70                     else//k==j
71                         dp[i][j] = min(dp[i][j], dp[i-1][j] + dl[ch[i-1]][ch[i]]);
72                 }
73         cout << *min_element(dp[r-1], dp[r-1] + n) <<endl;
74     }
75     return 0;
76 }
77 
78 AOJ2200

AOJ2200 CN

最小生成树

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N = 500002;
 6 int n,m,ans,h;
 7 int par[N], _rank[N];
 8 
 9 struct edge{
10     int x, y, d;
11     const bool operator < (const edge& o) const
12     {
13      return d < o.d;   //排序
14     }
15 }zhen[500002];
16 
17 void initialize(){
18     for(int i = 1; i < N; i++) par[i] = i, _rank[i] = 0;
19 }
20 
21 int find(int x){
22     if(x == par[x]) return x;
23     return par[x] = find(par[x]);
24 }
25 
26 void unit(int x, int y){
27     int xx = find(x), yy = find(y);
28     if(xx == yy) return;
29     if(_rank[xx] < _rank[yy]) par[xx] = yy;
30     else
31         par[yy] = xx;
32         if(_rank[xx] == _rank[yy]) _rank[x]++;
33 }
34 
35 bool is_thesame(int x, int y){return find(x) == find(y);}
36 
37 
38 int main()
39 {
40     while(cin >> n >> m)
41     {
42         initialize();
43         ans = 0;
44      for(int i = 0; i < m; i++)
45         cin >> zhen[i].x >> zhen[i].y >> zhen[i].d;
46      sort(zhen, zhen + m);
47      for(int i = 0; i < m; i++)
48      {
49          if(!is_thesame(zhen[i].x,zhen[i].y))
50          {
51              ans += zhen[i].d;
52              unit(zhen[i].x,zhen[i].y);
53          }
54      }
55      for(h = 1; h <= n; h++)
56         if(find(h) != find(1)) break;
57          if(h != n+1)
58              cout << "No" <<endl;
59          else
60              cout <<  233333333-ans <<endl;
61     }
62     return 0;
63 }

GOJ1379

 1 //kruskal
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int g[20010], ans, n, m, r;
 8 
 9 struct stu{
10     int x, y, cost;
11 }ch[50010];
12 
13 int find(int k){
14     if(g[k] == -1) return k;
15     return g[k] = find(g[k]);
16 }
17 
18 bool isthesame(int x, int y) {
19     int a = find(x), b = find(y);
20     if(a==b) return false;
21     g[a] = b;
22     return true;
23 }
24 
25 bool cmp(stu a,stu b){
26     return a.cost > b.cost;
27 }
28 
29 void kruskal(){
30     sort(ch, ch + r, cmp);
31     for(int i = 0; i < r; i++)
32     if(isthesame(ch[i].x, n + ch[i].y))//+n是区别男女兵
33         ans += ch[i].cost;
34 }
35 
36 
37 int main()
38 {
39     int T;
40     scanf("%d",&T);
41     while (T--)
42     {
43         ans = 0;
44         scanf("%d%d%d",&n, &m, &r);
45         memset(g, -1, sizeof(int) * (n + m));
46         for(int i = 0; i < r; i++)
47             scanf("%d%d%d",&ch[i].x, &ch[i].y, &ch[i].cost);
48         kruskal();
49         printf("%d
", 10000 * (n + m) - ans);
50     }
51     return 0;
52 }

POJ3723

 1 #include <iostream>
 2 #include <math.h>
 3 #define INF 100007
 4 using namespace std;
 5 int d[102][102], n;
 6 bool used[102];
 7 int mincost[102];
 8 
 9 int prim(){
10     for(int i = 0; i < 102; i++)
11     {
12         mincost[i] = INF;
13         used[i] = false;
14     }
15 
16     mincost[0] = 0;
17     int ans = 0;
18     while(true)
19     {
20         int flag = -1;
21         for(int i = 0; i < n; i++)
22             if(!used[i] && (flag == -1 || mincost[i]< mincost[flag]))
23                 flag = i;
24 
25         if(flag == -1)
26             break;
27 
28         used[flag] = true;
29         ans += mincost[flag];
30         for(int i = 0; i < n; i++)
31             mincost[i] = min(mincost[i], d[flag][i]);
32     }
33     return ans;
34 }
35 
36 
37 int main()
38 {
39     while(cin >> n)
40     {
41         for(int i = 0; i < n; i++)
42             for(int k = 0; k < n; k++)
43                 cin >> d[i][k];
44         cout << prim() << endl;
45     }
46     return 0;
47 }

POJ1258

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int unit[1002];
 6 int ans = 0,n,m;
 7 
 8 struct stu{
 9     int from, to, cost;
10 }edge[20002];
11 
12 int cmp(const stu &a, const stu &b){
13     return a.cost > b.cost;
14 }
15 
16 void init_union(int n){
17     for(int i = 1; i <= n; i++)
18         unit[i] = i;
19 }
20 
21 int find(int x){
22     if(unit[x] == x) return x;
23     return unit[x] = find(unit[x]);
24 }
25 
26 bool isthesame(int x, int y){
27     int a = find(x), b = find(y);
28     if(a == b) return false;
29     else
30         unit[a] = b;
31     return true;
32 }
33 
34 void kruskal(){
35     init_union(n);
36     for(int i = 1; i <= m; i++)
37         if(isthesame(edge[i].from, edge[i].to))
38            {
39              ans += edge[i].cost;
40             /// cout  << edge[i].from <<" "<<edge[i].to <<" "<< edge[i].cost<<" "<<ans <<endl;
41            }
42 }
43 
44 
45 int main()
46 {
47     cin >> n >> m;
48     for(int i = 1; i <= m; i++)
49         cin >> edge[i].from >> edge[i].to >> edge[i].cost;
50     sort(edge+1, edge + m + 1, cmp);
51     kruskal();
52     int q = find(1);
53     int flag = 1;
54     for(int i = 2; i <= n; i++)
55         if(find(i) != q)flag = 0;
56     if(flag)
57         cout << ans << endl;
58     else cout << "-1
";
59     return 0;
60 }

POJ2377

 1 #include <iostream>
 2 #include <math.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #define Max 10010
 6 using namespace std;
 7 
 8 int unit[Max*2],n,m;
 9 
10 struct st{
11     int from, to;
12     double cost;
13 }edge[Max*Max];
14 
15 pair<int, int> ch[Max*2];
16 
17 void init(int n){
18     for(int i = 0; i <= n; i++)
19         unit[i] = i;
20 }
21 
22 int cmp(st a, st b){
23     return a.cost > b.cost;
24 }
25 
26 int find(int k){
27     if(unit[k] == k) return k;
28     return unit[k] = find(unit[k]);
29 }
30 
31 int isthesame(int a, int b){
32     int x = find(a), y = find(b);
33     if(x == y) return false;
34     else
35     {
36         //cout<<x<<"  "<<y<<endl;
37         unit[x] = y;
38         return true;
39     }
40 }
41 
42 double kruskal(){
43     sort(edge+1, edge + m + 1, cmp);
44     init(n);
45     double ans = 0;
46     for(int i = 1; i <= m; i++)
47     {
48         if(isthesame(edge[i].from, edge[i].to))
49         {
50             ans += edge[i].cost;
51         }
52     }
53     return ans;
54 }
55 
56 int main()
57 {
58     int a,b,x,y;
59     cin >> n >> m;
60     for(int i = 1; i <= n; i++)
61     {
62         cin >> a >> b;
63         ch[i] = {a,b};
64     }
65     double allcost = 0;
66     for(int i = 1; i <= m; i++)
67     {
68         cin >> x >> y;//genhao x-x1^2+y-y1^2
69         double cost = sqrt((ch[x].first-ch[y].first)*(ch[x].first-ch[y].first)
70                            +(ch[x].second-ch[y].second)*(ch[x].second-ch[y].second));
71         allcost += cost;
72         edge[i] = {x, y, cost};
73        // cout << cost<<endl;
74     }
75     printf("%.3f
", allcost - kruskal());
76     return 0;
77 }

AOJ2224

 1 #include <iostream>//求最小生成树中的最长边
 2 #include <math.h>
 3 #define MAX 2050
 4 #define INF 1000000010
 5 using namespace std;
 6 
 7 int n,m;
 8 bool used[MAX];
 9 long long mincost[MAX];
10 long long cost[MAX][MAX];
11 
12 long long prim(){
13     long long longest = 0;
14 
15     for(int i = 0; i <= n+1; i++)
16     {
17         mincost[i] = INF;
18         used[i] = false;
19     }
20     mincost[0] = 0;
21 
22     while(true)
23     {
24         int flag = -1;
25         for(int i = 0; i < n; i++)
26             if(!used[i] &&(flag == -1 || mincost[i] < mincost[flag])) 
27                 flag = i;
28 
29         if(flag == -1) break;
30         used[flag] = true;
31         longest = max(longest, mincost[flag]);//最长边
32         for(int i = 0; i < n; i++)
33             mincost[i] = min(mincost[i], cost[flag][i]);
34     }
35     return longest;
36 }
37 
38 int main()
39 {
40     cin >> n >> m;
41     for(int i = 0; i <= n+1; i++)
42         for(int k = 0; k <= n+1; k++)
43         {
44             if(i==k) cost[i][k] = 0;
45             cost[i][k] = INF;
46         }
47     for(int i = 0; i < m; i++)
48     {
49         int a,b;
50         long long c;
51         cin >> a >> b >> c;
52         a--;b--;
53         cost[b][a] = cost[a][b] = min(cost[a][b], c);//忘了设置双向路wa了几次
54     }
55     cout << prim() << endl;
56     return 0;
57 }

POJ2395

 1 #include <iostream>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 #define INF 0x3f3f3f3f
 5 using namespace std;
 6 
 7 struct edge{
 8     int u,v;
 9 }ed[1009];
10 
11 int n,z;
12 int d[1009],p[1009];
13 int _rank[1009];
14 
15 void init(){
16     for(int i = 1; i <= n; i++)
17     {
18         d[i] = i;
19         _rank[i] = 0;
20     }
21 }
22 
23 int find(int x){
24     if(d[x] != x)
25         d[x] = find(d[x]);
26     return d[x];
27 }
28 
29 void unite(int x,int y){
30     int a = find(x), b = find(y);
31     if(a == b) return;
32     if(_rank[a] < _rank[b]) d[a] = b;
33     else
34     {
35         d[b] = a;
36         if(_rank[a] == _rank[b]) _rank[x]++;
37     }
38 }
39 
40 double dis(edge x,edge y){//剧毒啊，这个返回值一直忘了改double
41     return sqrt(1.0*(x.u-y.u)*(x.u-y.u) + 1.0*(x.v-y.v)*(x.v-y.v));
42 }
43 
44 int main()
45 {
46     cin >> n >> z;
47     init();
48     for(int i = 1; i <= n; i++)
49     {//1-n电脑的坐标
50         cin >> ed[i].u >> ed[i].v;
51     }
52     char a[20];
53     int b,c;
54     int cou = 0;
55     while(cin >> a)
56     {
57         if(a[0] == 'O')
58         {//修理了的才能并，并且修理的是第b台
59             cin >> b;
60             for(int i = 0; i < cou; i++)
61                 if(dis(ed[b],ed[p[i]]) <= z)//距离必须小于等于z
62                     unite(b,p[i]);
63             p[cou++] = b;
64         }
65         else if(a[0] == 'S')
66         {
67             cin >> b >> c;
68             //cout << find(b) <<" "<<find(c)<<endl;
69             if(find(b) == find(c))
70                 cout << "SUCCESS" <<endl;
71             else cout << "FAIL" <<endl;
72         }
73     }
74     return 0;
75 }

POJ2236

并查集

 1 #include <stdio.h>
 2 
 3 int d[200009];
 4 
 5 void init(int n){
 6     for(int i = 0; i <= n+1; i++)
 7         d[i] = i;
 8 }
 9 
10 int find(int x){
11     if(d[x] == x)
12         return x;
13     return d[x] = find(d[x]);
14 }
15 
16 bool thesame(int x,int y){
17     return find(x) == find(y);
18 }
19 
20 void unite(int x,int y){
21     int a = find(x), b = find(y);
22     if(a==b) return;
23     d[a] = b;
24 }
25 
26 int main()
27 {
28     int T;
29     scanf("%d",&T);
30     while(T--)
31     {
32         int n, m, i;
33         scanf("%d%d",&n,&m);
34         init(2*n);
35         for(int i = 0; i < m; i++)
36         {
37             getchar();
38             char a;
39             int b,c;
40             scanf("%c%d%d",&a,&b,&c);
41             if(a == 'A')
42             {
43                 if(thesame(b, c))
44                     printf("In the same gang.
");
45                 else if(thesame(b, c+n))
46                     printf("In different gangs.
");
47                 else printf("Not sure yet.
");
48             }
49             else
50             {
51                 unite(b, c+n);
52                 unite(b+n, c);
53             }
54         }
55     }
56     return 0;
57 }

POJ1703

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MAX_N 200010
 5 
 6 int A[MAX_N];
 7 int rev[MAX_N*2], sa[MAX_N *2];
 8 int n,k;
 9 int rank1[MAX_N], tmp[MAX_N];
10 
11 bool compare_sa(int i, int j){
12     if(rank1[i] != rank1[j])
13         return rank1[i] < rank1[j];
14     int ri = i + k <= n ? rank1[i+k] : -1;
15     int rj = j + k <= n ? rank1[j+k] : -1;
16     return ri < rj;
17 }
18 
19 void construct_sa(int sh[],int n,int *sa){
20     for(int i = 0; i <= n; i++){
21         sa[i] = i;
22         rank1[i] = i < n ? sh[i] : -1;
23     }
24 
25     for(k = 1; k <= n; k *= 2){
26         sort(sa, sa + n + 1, compare_sa);
27 
28         tmp[sa[0]] = 0;
29         for( int i = 1; i <= n; i++){
30             tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i])? 1 : 0);
31         }
32         for(int i = 0; i <= n; i++){
33             rank1[i] = tmp[i];
34         }
35     }
36 }
37 
38 void solve(){
39     reverse_copy(A, A+n, rev);
40     construct_sa(rev, n, sa);
41 
42     int p1;
43     for(int i = 0; i < n; i++){
44         p1 = n - sa[i];
45         if(p1 >= 1 && n - p1 >=2)
46             break;
47     }
48 
49     int m = n-p1;
50     reverse_copy(A+p1, A+n, rev);
51     reverse_copy(A+p1, A+n, rev+m);
52     construct_sa(rev, m*2, sa);
53 
54     int p2;
55     for(int i = 0; i <= 2*n; i++){
56         p2 = p1 + m -sa[i];
57         if(p2 - p1 >= 1 && n - p2 >= 1)
58             break;
59     }
60 
61     reverse(A, A+p1);
62     reverse(A+p1, A+p2);
63     reverse(A+p2, A+n);
64     for(int i = 0; i < n; i++)
65         printf("%d
", A[i]);
66     //cout << "p1=" << p1 << " "<<p2 <<endl;
67 }
68 
69 int main(){
70     scanf("%d",&n);
71     for(int i = 0; i < n; i++)
72         scanf("%d",&A[i]);
73     solve();
74 
75     return 0;
76 }

POJ3581

 1 //SA_LCP
 2 
 3 #include <iostream>
 4 #include <string.h>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 char S[11111];
 9 char T[11111];
10 int rank1[11111], lcp[11111], sa[11111], tmp[11111];
11 int n, k, sl;
12 
13 void construct_lcp(string S, int *sa, int *lcp){
14 
15     for(int i = 0; i <= n; i++)
16         rank1[sa[i]] = i;
17     int h = 0;
18     lcp[0] = 0;
19     for(int i = 0; i < n; i++){
20         int j = sa[rank1[i] - 1];
21 
22         if(h > 0) h--;
23         for(; j + h < n && i + h < n; h++)
24             if(S[j+h] != S[i+h])
25                 break;
26         lcp[rank1[i]-1] = h;
27     }
28 }
29 
30 bool compare_sa(int i, int j){
31     if(rank1[i] != rank1[j])
32         return rank1[i] < rank1[j];
33     int ri = i + k <= n ? rank1[i+k] : -1;
34     int rj = j + k <= n ? rank1[j+k] : -1;
35     return ri < rj;
36 }
37 
38 
39 void construct_sa(string sh, int *sa){
40     for(int i = 0; i <= n; i++){
41         sa[i] = i;
42         rank1[i] = i < n ? sh[i] : -1;
43     }
44     for(k = 1; k <= n; k *= 2){
45         sort(sa, sa + n + 1, compare_sa);
46 
47         tmp[sa[0]] = 0;
48         for( int i = 1; i <= n; i++){
49             tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i])? 1 : 0);
50         }
51         for(int i = 0; i <= n; i++){
52             rank1[i] = tmp[i];
53         }
54     }
55 }
56 
57 void solve(){
58     for(int i = 0; i <= n; i++)
59         lcp[i] = 0;
60     construct_sa(S,sa);
61     construct_lcp(S,sa,lcp);
62 
63     int ans = 0;
64     for(int i = 0; i < n; i++)
65         if((sa[i]<sl)!=(sa[i+1]<sl))
66             ans = max(ans, lcp[i]);
67 
68     printf("Nejdelsi spolecny retezec ma delku %d.
", ans);
69 }
70 
71 int main(){
72     int t;
73     cin >> t;
74     getchar();
75     while(t--){
76         gets(S);
77         gets(T);
78         sl = strlen(S);
79         char str1[10] = "$";
80         //cout << S <<endl;
81         strcat(S, str1);
82         //cout << S <<endl;
83         strcat(S, T);
84         //cout << S <<"~~"<<endl;
85         n = strlen(S);
86         solve();
87     }
88     return 0;
89 }

POJ2217

  1 最长回文子序列
  2 
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <bits/stdc++.h>
  6 #include <math.h>
  7 using namespace std;
  8 
  9 int rank1[2010], temp[2010], lcp[2010], sa[2010];
 10 int a[25][2010];
 11 char s[2020],t[2010];
 12 int n, k, g;
 13 
 14 bool compare_sa(int i, int j){
 15     if(rank1[i] != rank1[j])
 16         return rank1[i] < rank1[j];
 17     int ri = i + k <= g ? rank1[i+k] : -1;
 18     int rj = j + k <= g ? rank1[j+k] : -1;
 19     return ri < rj;
 20 }
 21 
 22 void construct_sa(string sh, int *sa){
 23     for(int i = 0; i <= g; i++){
 24         sa[i] = i;
 25         rank1[i] = i < g ? sh[i] : -1;
 26     }
 27 
 28     for(k = 1; k <= g; k <<= 1){
 29         sort(sa, sa+g+1, compare_sa);
 30 
 31         temp[sa[0]] = 0;
 32         for(int i = 1; i <= g; i++){
 33             temp[sa[i]] = temp[sa[i-1]] + (compare_sa(sa[i-1],sa[i])?1:0);
 34         }
 35         for(int i = 0; i <= g; i++)
 36             rank1[i] = temp[i];
 37     }
 38 
 39 }
 40 
 41 void construct_lcp(string sh, int *sa, int *lcp){
 42     for(int i = 0; i <= g; i++)
 43         rank1[sa[i]] = i;
 44     int h = 0;
 45     lcp[0] = 0;
 46     for(int i = 0; i < g; i++){
 47         int j = sa[rank1[i] -1];
 48 
 49         if(h > 0) h--;
 50         for(;j+h<g && i+h<g; h++)
 51             if(sh[j+h] != sh[i+h])
 52                 break;
 53         lcp[rank1[i]-1] = h;
 54     }
 55 }
 56 
 57 
 58 void construct_rmq(int *lcp){
 59     memset(a,-1,sizeof(a));
 60     for(int i = 1; i <= g; i++)
 61         a[0][i-1] = lcp[i];
 62     //for(int i = 1; i <= g; i++)
 63         //cout << a[0][i-1]<<" ";
 64         //cout <<endl;
 65     for(int k = 1; (1<<k) <= g; k++){
 66         for(int i = 0; (i+(1<<k))-1 < g; i++){
 67             a[k][i] = min(a[k-1][i], a[k-1][i+(1<<(k-1))]);
 68             //cout << a[k][i]<<" ";
 69         }
 70         //cout <<endl;
 71     }
 72 }
 73 
 74 
 75 int query(int l,int r){
 76     int k=0;
 77      while(1<<(k+1)<=(r-l+1))
 78         k++;
 79      //cout<<a[k][l-1]<<" # " <<a[k][r-(1<<k)+1-1]<<endl;
 80      return min(a[k][l-1],a[k][r-(1<<k)+1-1]);
 81 }
 82 
 83 int lcp1(int a,int b){
 84      int l=rank1[a], r=rank1[b];
 85      if(r<l) swap(l,r); 
 86      l--, r--;
 87      if(r<0) return 0;
 88      return query(l+1,r);//l+1
 89 }
 90 
 91 
 92 int main(){
 93     char str[1010];
 94     scanf("%s", str);
 95         int n = strlen(str);
 96         for(int i = 0; i < n; i++)
 97             s[i] = str[i];
 98         for(int i = 0; i < n; i++)
 99             s[i+n+1] = str[n-i-1];
100         s[n] = 1;
101         s[2*n+1] = 0;
102         g = n*2+1;
103         construct_sa(s,sa);
104         construct_lcp(s,sa,lcp);
105         for(int i = 0; i <= g; i++)
106             rank1[sa[i]] = i;
107         construct_rmq(lcp);
108         int ans = 0;
109 
110         int fron,tmp;
111         for(int i=0;i<g;i++){
112             tmp=lcp1(i,g-i-1);
113             if(2*tmp-1>ans){  //对称个数为奇数
114                 ans=2*tmp-1;
115                 fron=i-tmp+1;
116             }
117             tmp=lcp1(i,g-i);
118             if(2*tmp>ans)  {  //对称个数为偶数
119                 ans=2*tmp;
120                 fron=i-tmp;
121             }
122         }//cout <<"~"<<fron<<" "<<ans<<endl;
123         str[fron+ans]='';
124         printf("%s
",str+fron);
125     return 0;
126 }

URAL1297