{purple11}

重新开始学习图论了

Common Subexpression Elimination

表达式树，，关于递归还是不会写

原文：http://www.cnblogs.com/zyb993963526/p/6385608.html

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 
 8 const int maxn = 60000;
 9 char s[maxn * 5], *p;
10 int cnt, kase;
11 int vis[maxn];
12 
13 struct node
14 {
15     string s;   //因为运算数是1~4个小写字母，所以这里要用string
16     int left, right;
17     bool operator < (const node& rhs)  const     //有map，所以一定要重载
18     {
19         if (s != rhs.s)       return s < rhs.s;
20         if (left != rhs.left)    return left < rhs.left;
21         return right < rhs.right;
22     }
23 }tree[maxn];
24 
25 map<node, int>dict;
26 
27 int solve()
28 {
29     int id = ++cnt;  //从1开始编号
30     node& t = tree[id];  //引用，比较方便
31     t.s = "";
32     t.left = t.right = -1;
33     while (*p >= 'a' && *p <= 'z')   //先把根输入进去
34     {
35         t.s.push_back(*p);
36         p++;
37     }
38 
39     //递归处理左右子树
40     if (*p == '(')
41     {
42         p++;  //跳过'('
43         t.left = solve(),  p++;     //跳过','
44         t.right = solve(), p++;     //跳过')'
45     }
46 
47     if (dict.count(t))   //如果已经出现过
48     {
49         cnt--;
50         return dict[t];   //直接返回子树编号
51     }
52     return dict[t] = id;  //没出现过，编号并返回
53 }
54 
55 
56 void print(int u)
57 {
58     if (vis[u]==kase)     cout << u ;   //如果子树已经输出过，直接输出编号
59     else
60     {
61         vis[u] = kase;
62         cout << tree[u].s;
63         //递归输出左右子树
64         if (tree[u].left != -1)
65         {
66             cout << "(";
67             print(tree[u].left);
68             cout << ",";
69             print(tree[u].right);
70             cout << ")";
71         }
72     }
73 }
74 
75 int main()
76 {
77     int T;
78     cin >> T;
79     for (kase = 1; kase <= T;kase++)
80     {
81         dict.clear();
82         cnt = 0;
83         cin >> s;
84         p = s;
85         print(solve());  //返回根编号，递归输出
86         cout << endl;
87     }
88     return 0;
89 }

View Code

Slim Span

UVA - 1395

求最大边权差最小的生成树

枚举最小边即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxe=10010;
 4 struct Edge
 5 {
 6     int u,v,w;
 7     bool operator <(const Edge &a)const
 8     {
 9         return w<a.w;
10     }
11 }e[maxe];
12 int n,m;
13 int slim;
14 int f[110];
15 
16 int gf(int x)
17 {
18     return x==f[x]?x:f[x]=gf(f[x]);
19 }
20 void kruskal(int x)
21 {
22     int cnt=0,temp=0;
23     for(int i=0;i<=n;i++) f[i]=i;  //初始化
24     int i;
25     for(i=x;i<m;i++)
26     {
27         int pu=gf(e[i].u);
28         int pv=gf(e[i].v);
29         if(pu!=pv)
30         {
31             cnt++;
32             f[pu]=pv;
33             if(cnt==n-1) break;
34         }
35     }
36     if(cnt!=n-1) return ;
37     temp=e[i].w-e[x].w;
38     if(x==0||temp<slim) slim=temp;
39     return ;
40 }
41 
42 int main()
43 {
44     while(scanf("%d%d",&n,&m)&&(n||m))
45     {
46         slim=-1;
47         for(int i=0;i<m;i++)
48             scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
49         sort(e,e+m);
50         for(int i=0;i+n-2<m;i++)  //
51             kruskal(i);
52         printf("%d
",slim);
53     }
54 }

View Code

Buy or Build

UVA - 1151

之前做过

先求一次mst，记录下选取的边。

易知如果选择套餐，一定不会再去选其它的边，只需考虑第一次mst中的边是否还需要即可。

二进制枚举所有方案。

  1 #include <bits/stdc++.h>
  2 #define ll long long
  3 using namespace std;
  4 vector<int> mst;
  5 const int maxn=1010;
  6 int qsize[10],qcost[10],q[10][maxn];
  7 int x[maxn],y[maxn];
  8 int f[maxn];
  9 int cnt,ans;
 10 
 11 struct edge
 12 {
 13     int u,v,w;
 14     bool operator < (const edge &a )const
 15     {
 16         return w<a.w;
 17     }
 18 }e[maxn*maxn];
 19 
 20 int t,n,m;
 21 void init()
 22 {
 23     for(int i=0;i<=n;i++) f[i]=i;
 24     ans=0;
 25     cnt=0;
 26     mst.clear();
 27 }
 28 
 29 int gf(int x)
 30 {
 31     return x==f[x]?f[x]:f[x]=gf(f[x]);
 32 }
 33 
 34 void uni(int a,int b)
 35 {
 36     int pa=gf(a);
 37     int pb=gf(b);
 38     f[pa]=pb;
 39 }
 40 
 41 int gd(int i,int j)
 42 {
 43     int dx=x[i]-x[j];
 44     int dy=y[i]-y[j];
 45     return dx*dx+dy*dy;
 46 }
 47 
 48 void add(int u,int v,int w)
 49 {
 50     e[cnt].u=u;
 51     e[cnt].v=v;
 52     e[cnt].w=w;
 53     cnt++;
 54 }
 55 
 56 
 57 void krustal()
 58 {
 59     int coun=0;
 60     for(int i=0;i<cnt;i++)
 61     {
 62         int pu=gf(e[i].u);
 63         int pv=gf(e[i].v);
 64         if(pu!=pv)
 65         {
 66             f[pu]=pv;
 67             ans+=e[i].w;
 68             mst.push_back(i);
 69             coun++;
 70             if(coun==n-1) break;
 71         }
 72     }
 73 }
 74 
 75 void mincost ()
 76 {
 77 
 78     for(int s=1;s<(1<<m);s++)  //枚举
 79     {
 80         int temp=0;
 81         for(int i=0;i<=n;i++) f[i]=i;    //初始化
 82         for(int i=0;i<m;i++) if(s&(1<<i))
 83         {
 84             temp+=qcost[i];
 85             for(int j=0;j<qsize[i];j++)
 86                 for(int k=j+1;k<qsize[i];k++)
 87                 {
 88                     int pj=gf(q[i][j]);
 89                     int pk=gf(q[i][k]);
 90                     if(pj!=pk) f[pj]=pk;
 91                 }
 92         }
 93     int len=mst.size();
 94     for(int i=0;i<len;i++)
 95     {
 96         int j=mst[i];
 97         int pu=gf(e[j].u);
 98         int pv=gf(e[j].v);
 99         if(pu!=pv)
100         {
101             temp+=e[j].w;
102             f[pu]=pv;
103         }
104     }
105     ans=min(ans,temp);
106     }
107 }
108 
109 int main()
110 {
111     scanf("%d",&t);
112     while(t--)
113     {
114         scanf("%d%d",&n,&m);
115         init();
116         for(int i=0;i<m;i++)
117         {
118             scanf("%d%d",&qsize[i],&qcost[i]);
119             for(int j=0;j<qsize[i];j++)
120                 scanf("%d",&q[i][j]);
121         }
122         for(int i=1;i<=n;i++)
123         {
124             scanf("%d%d",&x[i],&y[i]);
125         }
126         for(int i=1;i<n;i++)
127             for(int j=i+1;j<=n;j++)
128              add(i,j,gd(i,j));
129         sort(e,e+cnt);
130         krustal();
131         mincost();
132         printf("%d
",ans);
133         if(t) printf("
");
134     }
135 }

View Code

Calling Circles

UVA - 247

之前刷过

floyd+dfs

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=30;
 4 map<string,int> namecode;
 5 string codename[maxn];
 6 int p[maxn][maxn];
 7 int vis[maxn];
 8 int n,m;
 9 void floyd()
10 {
11     for(int k=1;k<=n;k++)
12         for(int i=1;i<=n;i++)
13         if(p[i][k]) for(int j=1;j<=n;j++)
14          if(p[k][j]) p[i][j]=1;
15          
16          //p[i][j]=p[i][j]||p[i][k]&&p[k][j];  //传递闭包
17 }
18 
19 void dfs(int u)
20 {
21     vis[u]=1;
22     for(int i=1;i<=n;i++)
23     if(!vis[i]&&p[u][i]&&p[i][u])
24     {
25         cout<<", "<<codename[i];
26         dfs(i);
27     }
28 }
29 int main()
30 {
31 
32    int cas=0;
33    string a,b;
34    while(scanf("%d%d",&n,&m)&&(n||m))
35    {
36        memset(p,0,sizeof(p));
37        memset(vis,0,sizeof(vis));
38        namecode.clear();
39        int id=0;
40        while(m--)
41        {
42            cin>>a>>b;
43            if(!namecode.count(a)) { namecode[a]=++id;codename[id]=a;  }
44            if(!namecode.count(b)) { namecode[b]=++id;codename[id]=b;  }
45            int u=namecode[a];
46            int v=namecode[b];
47            p[u][v]=1;
48        }
49        if(cas>1)  puts("");
50        printf("Calling circles for data set %d:
",++cas);
51        floyd();
52        for(int i=1;i<=n;i++) if(!vis[i])
53        {
54             cout<<codename[i];
55             dfs(i);
56             puts("");
57        }
58    }
59    return 0;
60 }

View Code

Audiophobia

UVA - 10048

floyd

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=110;
 6 const int inf=0x3f3f3f3f;
 7 int p[maxn][maxn];
 8 int n,m,q;
 9 void floyd()
10 {
11     for(int k=1;k<=n;k++)
12         for(int i=1;i<=n;i++)
13         for(int j=1;j<=n;j++)
14     {
15         int temp=max(p[i][k],p[k][j]);
16         p[i][j]=min(temp,p[i][j]);
17     }
18 }
19 
20 int main()
21 {
22 
23     int u,v,w;
24     int cas=0;
25     while(scanf("%d%d%d",&n,&m,&q)&&(n||m||q))
26     {
27          for(int i=1;i<=n;i++)
28             for(int j=1;j<=n;j++)
29                 p[i][j]=i==j?0:inf;
30         for(int i=0;i<m;i++)
31         {
32             scanf("%d%d%d",&u,&v,&w);
33             p[u][v]=p[v][u]=w;
34         }
35 
36 
37         floyd();
38         if(cas>0) puts("");
39         printf("Case #%d
",++cas);
40         while(q--)
41         {
42             scanf("%d%d",&u,&v);
43             if(p[u][v]==inf) puts("no path");
44             else printf("%d
",p[u][v]);
45         }
46     }
47 }

View Code