{white5}

接着紫书图论开始刷。。。

Fire!

先从所有火源bfs1求出任意方格的起火时间，再从人开始bfs2逃跑。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=1050;
  4 char pic[maxn][maxn];
  5 int vis[maxn][maxn];
  6 int dead[maxn][maxn];
  7 int n,m;
  8 int dir[4][2]={0,1,0,-1,1,0,-1,0};
  9 struct node
 10 {
 11     int x,y;
 12     int st;
 13     node(int x=0,int y=0,int st=0):x(x),y(y),st(st){}
 14 }now,nex;
 15 
 16 queue<node>q;
 17 bool inside(node no)
 18 {
 19     if(no.x>=0&&no.x<n&&no.y>=0&&no.y<m) return 1;
 20     return 0;
 21 }
 22 void bfs1()
 23 {
 24     memset(vis,0,sizeof(vis));
 25     while(!q.empty()) q.pop();
 26     for(int i=0;i<n;i++)
 27         for(int j=0;j<m;j++)
 28         {
 29             dead[i][j]=0x3f3f3f3f;
 30             if(pic[i][j]=='F')
 31             {
 32                 q.push(node(i,j,0));
 33                 dead[i][j]=0;
 34                 vis[i][j]=1;
 35             }
 36 
 37         }
 38     while(!q.empty())
 39     {
 40         now=q.front();
 41         q.pop();
 42         for(int i=0;i<4;i++)
 43         {
 44             nex.x=now.x+dir[i][0];
 45             nex.y=now.y+dir[i][1];
 46             if(inside(nex)&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]!='#')
 47             {
 48                 vis[nex.x][nex.y]=1;
 49                 dead[nex.x][nex.y]=dead[now.x][now.y]+1;
 50                 q.push(nex);
 51             }
 52         }
 53 
 54     }
 55     return ;
 56 }
 57 int bfs2()
 58 {
 59     while(!q.empty()) q.pop();
 60     memset(vis,0,sizeof(vis));
 61     for(int i=0;i<n;i++)
 62         for(int j=0;j<m;j++)
 63     if(pic[i][j]=='J')  {
 64         q.push(node(i,j,0));
 65         vis[i][j]=1;
 66         break;
 67     }
 68     while(!q.empty())
 69     {
 70         now=q.front();
 71         q.pop();
 72         if(now.x==0||now.x==n-1||now.y==0||now.y==m-1) return now.st+1;
 73         for(int i=0;i<4;i++)
 74         {
 75             nex.x=now.x+dir[i][0];
 76             nex.y=now.y+dir[i][1];
 77             nex.st=now.st+1;
 78             if(inside(nex)&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]!='#'&&nex.st<dead[nex.x][nex.y])
 79             {
 80                 vis[nex.x][nex.y]=1;
 81                 q.push(nex);
 82             }
 83         }
 84     }
 85     return -1;
 86 }
 87 int main()
 88 {
 89     int t;
 90     scanf("%d",&t);
 91     while(t--)
 92     {
 93         scanf("%d%d",&n,&m);
 94         for(int i=0;i<n;i++)
 95                 scanf("%s",pic[i]);
 96         bfs1();
 97         int ans=bfs2();
 98         if(ans!=-1) printf("%d
",ans);
 99         else puts("IMPOSSIBLE");
100     }
101 }

View Code

The Monocycle

UVA - 10047

其实只是简单的一个bfs

因为一点小错误搞了很久，代码也写得很拉杂。。。

看到别人代码vis数组可以省去，dis可以直接放结构体里方便些

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=30;
 4 const int inf=0x3f3f3f3f;
 5 int d[maxn][maxn][4][5];
 6 int vis[maxn][maxn][4][5];
 7 int dir[4][2]={-1,0,0,1,1,0,0,-1};
 8 char g[maxn][maxn];
 9 int n,m;
10 int sx,sy,ex,ey;
11 struct node
12 {
13     int x,y,d,c;
14     node(int x=0,int y=0,int d=0,int c=0):x(x),y(y),d(d),c(c){}
15 };
16 int bfs()
17 {
18     queue<node> q;
19     for(int i=0;i<n;i++)
20         for(int j=0;j<m;j++)
21         for(int k=0;k<4;k++)
22         for(int l=0;l<5;l++)
23     {
24         d[i][j][k][l]=inf;
25         vis[i][j][k][l]=0;
26     }
27     d[sx][sy][0][0]=0;
28     q.push(node(sx,sy,0,0));
29     vis[sx][sy][0][0]=1;
30     while(!q.empty())
31     {
32         node t=q.front();
33         q.pop();
34         if(t.x==ex&&t.y==ey&&t.c==0)
35         {
36             return d[ex][ey][t.d][0];
37         }
38         int dx=t.x+dir[t.d][0],dy=t.y+dir[t.d][1];
39         int dd=t.d,dc=(t.c+1)%5;
40         if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dx][dy][dd][dc]&&g[dx][dy]!='#')  //dc写成了dx找了半小时=_=||
41         {
42             d[dx][dy][dd][dc]=d[t.x][t.y][t.d][t.c]+1;
43             vis[dx][dy][dd][dc]=1;
44             q.push(node(dx,dy,dd,dc));
45         }
46         dx=t.x,dy=t.y;
47         dd=(t.d+1)%4,dc=t.c;
48         if(!vis[dx][dy][dd][dc])
49         {
50             d[dx][dy][dd][dc]=d[t.x][t.y][t.d][t.c]+1;
51             vis[dx][dy][dd][dc]=1;
52             q.push(node(dx,dy,dd,dc));
53         }
54         dx=t.x,dy=t.y;
55         dd=(t.d-1+4)%4,dc=t.c;
56          if(!vis[dx][dy][dd][dc])
57         {
58             d[dx][dy][dd][dc]=d[t.x][t.y][t.d][t.c]+1;
59             vis[dx][dy][dd][dc]=1;
60             q.push(node(dx,dy,dd,dc));
61         }
62     }
63     return inf;
64 }
65 int main()
66 {
67     int kase=0;
68     while(scanf("%d%d",&n,&m)&&(n||m))
69     {
70         for(int i=0;i<n;i++)
71         {
72             scanf("%s",g[i]);
73             for(int j=0;j<m;j++){
74                 if(g[i][j]=='S') {sx=i;sy=j;}
75                 if(g[i][j]=='T') {ex=i;ey=j;}
76             }
77         }
78         int ans=bfs();
79         if(kase) puts("");
80         printf("Case #%d
",++kase);
81         if(ans!=inf) printf("minimum time = %d sec
",ans);
82         else puts("destination not reachable");
83     }
84 
85 }

View Code

The Necklace

UVA - 10054

无向图的欧拉回路+输出路径

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int g[55][55];
 4 int f[55];
 5 int deg[55];
 6 int n;
 7 
 8 int gf(int x)
 9 {
10   return x==f[x]?x:f[x]=gf(f[x]);
11 }
12 
13 void dfs(int u)
14 {
15     for(int i=1;i<=50;i++) if(g[u][i])
16     {
17         g[u][i]--;
18         g[i][u]--;
19         dfs(i);
20         printf("%d %d
",i,u);
21     }
22 }
23 int main()
24 {
25     int t;
26     int kase=0;
27     scanf("%d",&t);
28     while(t--)
29     {
30         for(int i=0;i<=55;i++) f[i]=i;
31         memset(deg,0,sizeof(deg));
32         memset(g,0,sizeof(g));
33         scanf("%d",&n);
34         int u,v;
35         for(int i=0;i<n;i++)
36         {
37             scanf("%d%d",&u,&v);
38             g[u][v]++;
39             g[v][u]++;
40             deg[u]++;
41             deg[v]++;
42             int pu=gf(u);
43             int pv=gf(v);
44             if(pu!=pv) f[pu]=pv;
45         }
46         if(kase) puts("");
47         printf("Case #%d
",++kase);
48         int rt=0;
49         int flag=1;
50         for(int i=1;i<=50;i++) if(deg[i])
51         {
52             if(deg[i]&1) {
53                 flag=0;
54                 break;
55             }
56             if(rt==0) rt=gf(i);
57             else{
58                 int v=gf(i);
59                 if(v!=rt) {
60                     flag=0;
61                     break;
62                 }
63             }
64         }
65         if(flag)
66         {
67             dfs(rt);
68         }
69         else puts("some beads may be lost");
70     }
71 }

View Code

Play on Words

UVA - 10129

有向图欧拉路径

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<set>
 4 #include<iostream>
 5 #include<cctype>
 6 #include<string>
 7 #include<sstream>
 8 #include<algorithm>
 9 #include<map>
10 #define LL long long
11 using namespace std;
12 const int maxn=100010;
13 int in[30],out[30];
14 int f[30];
15 set<int> si;
16 void init()
17 {
18     for(int i=0;i<30;i++)
19     {
20         in[i]=0;
21         out[i]=0;
22         f[i]=i;
23     }
24 }
25 
26 int gf(int x)
27 {
28     return x==f[x]?x:f[x]=gf(f[x]);
29 }
30 
31 void uni(int a,int b)
32 {
33     int pa=gf(a);
34     int pb=gf(b);
35     f[pa]=pb;
36 }
37 string s;
38 int main()
39 {
40     int t;
41     scanf("%d",&t);
42     while(t--)
43     {
44         int ok=1;
45         si.clear();
46         init();
47         int n;
48         int a,b;
49         int ctin=0,ctout=0,ct=0;
50         scanf("%d",&n);
51         for(int i=0;i<n;i++)
52         {
53             cin>>s;
54             a=s[0]-'a';
55             b=s[s.length()-1]-'a';
56             si.insert(a);
57             si.insert(b);
58             in[a]++;
59             out[b]++;
60             if(gf(a)!=gf(b)) uni(a,b);
61         }
62         int u=gf(a);
63         for(set<int> ::iterator it=si.begin();it!=si.end();it++)
64         {
65             if(gf(*it)!=u) ct++;
66             if(ct>0) {ok=0;break;}
67             if(in[*it]-out[*it]==1) ctin++;
68             else if(in[*it]-out[*it]==-1) ctout++;
69             else if(in[*it]-out[*it]>1||in[*it]-out[*it]<-1) {ok=0;break;}
70             if(ctin>1||ctout>1) {ok=0;break;}
71         }
72 
73         if(ok) puts("Ordering is possible.");
74         else puts("The door cannot be opened.");
75     }
76 }

View Code

连通分量

Knights of the Round Table

UVALive - 3523

无向图的点的双联通分量

二分图的判定

题目要求的是不在任何一个奇圈上的人有几个

先求出所有的点双联通分量，如果该分量不是二分图说明有奇圈，有奇圈就说明每个人都可以参加至少一场会议（p317有证明，不难），把这些人标记，最后拿总人数减去这些人就是答案了。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxv=1010;
  4 const int maxe=1000010;
  5 
  6 int n,m;
  7 
  8 int g[maxv][maxv];
  9 struct Edge
 10 {
 11     int u,v,nex;
 12 }e[maxe<<1];
 13 int head[maxv];
 14 int cnt=0;
 15 void add(int u,int v)
 16 {
 17     e[cnt].u=u;
 18     e[cnt].v=v;
 19     e[cnt].nex=head[u];
 20     head[u]=cnt++;
 21 }
 22 void init()
 23 {
 24     memset(g,0,sizeof(g));
 25     memset(head,-1,sizeof(head));
 26     cnt=0;
 27 }
 28 
 29 int pre[maxv],iscut[maxv],bccno[maxv],dfsk,bcc_cnt;
 30 vector<int> bcc[maxv];
 31 stack<int> s;
 32 
 33 int dfs(int u,int f)
 34 {
 35     int lowu=pre[u]=++dfsk;
 36     int child=0;
 37     for(int i=head[u];i!=-1;i=e[i].nex)
 38     {
 39         int v=e[i].v;
 40         if(!pre[v])
 41         {
 42             s.push(i);
 43             child++;
 44             int lowv=dfs(v,u);
 45             lowu=min(lowu,lowv);
 46             if(lowv>=pre[u])
 47             {
 48                 iscut[u]=1;
 49                 bcc_cnt++;
 50                 bcc[bcc_cnt].clear(); //bcc从1开始编号
 51                 for(;;)
 52                 {
 53                     int te=s.top();
 54                     s.pop();
 55                     Edge p=e[te];
 56                     if(bccno[p.u]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.u);bccno[p.u]=bcc_cnt; }
 57                     if(bccno[p.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.v);bccno[p.v]=bcc_cnt; }
 58                     if(p.u==u&&p.v==v) break;
 59                 }
 60             }
 61         }
 62         else if(pre[v]<pre[u]&&v!=f)
 63         {
 64             s.push(i);
 65             lowu=min(lowu,pre[v]);
 66         }
 67     }
 68     if(f<0&&child==1) iscut[u]=0;
 69     return lowu;
 70 }
 71 
 72 void find_bcc(int n)
 73 {
 74     memset(pre,0,sizeof(pre));
 75     memset(iscut,0,sizeof(iscut));
 76     memset(bccno,0,sizeof(bccno));
 77     dfsk=bcc_cnt=0;
 78     for(int i=0;i<n;i++) if(!pre[i])
 79         dfs(i,-1);
 80 }
 81 
 82 int odd[maxv];  //是否可以参加会议
 83 int color[maxv];
 84 bool bipartite(int u,int b)
 85 {
 86     for(int i=head[u];i!=-1;i=e[i].nex)
 87     {
 88         int v=e[i].v;
 89         if(bccno[v]!=b) continue;
 90         if(color[u]==color[v]) return false;
 91         if(!color[v])
 92         {
 93             color[v]=3-color[u];
 94             if(!bipartite(v,b)) return false;
 95         }
 96     }
 97     return true;
 98 }
 99 int main()
100 {
101     
102 
103     while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
104     {
105         init();
106         int u,v;
107         for(int i=0;i<m;i++){
108             scanf("%d%d",&u,&v);
109             u--;v--;
110             g[u][v]=g[v][u]=1;
111         }
112         for(int i=0;i<n;i++)
113             for(int j=i+1;j<n;j++) if(!g[i][j])
114             {
115                 add(i,j);
116                 add(j,i);
117             }
118         find_bcc(n);
119 
120         memset(odd,0,sizeof(odd));
121         for(int i=1;i<=bcc_cnt;i++)
122         {
123             memset(color,0,sizeof(color));
124             for(int j=0;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;
125             int u=bcc[i][0];
126             color[u]=1;
127             if(!bipartite(u,i))
128                 for(int j=0;j<bcc[i].size();j++) odd[bcc[i][j]]=1;
129         }
130         int ans=n;
131         for(int i=0;i<n;i++) if(odd[i]) ans--;
132         printf("%d
",ans);
133     }
134     return 0;
135 }

View Code

下面这份代码有问题，，注释里写了

  1 #include <iostream>
  2 #include <cstring>
  3 #include <stack>
  4 #include <vector>
  5 #include <cstdio>
  6 using namespace std;
  7 const int maxv=1010;
  8 int A[maxv][maxv];
  9 int n,m;
 10 struct Edge
 11 {
 12     int u,v,nex;
 13 }e[maxv*maxv<<1];
 14 int head[maxv];
 15 int cnt=0;
 16 void init()
 17 {
 18     memset(head,-1,sizeof(head));
 19     cnt=0;
 20 }
 21 void add(int u,int v)
 22 {
 23     e[cnt].u=u;
 24     e[cnt].v=v;
 25     e[cnt].nex=head[u];
 26     head[u]=cnt++;
 27 }
 28 
 29 int pre[maxv],iscut[maxv],bccno[maxv],dfsk,bcc_cnt;
 30 stack<int> s;
 31 vector<int> bcc[maxv];
 32 
 33 int dfs(int u,int id)
 34 {
 35     int lowu=pre[u]=++dfsk;
 36     int child=0;
 37     for(int i=head[u];i!=-1;i=e[i].nex)
 38     {
 39         int v=e[i].v;
 40         if(i==(id^1)) continue;
 41         if(!pre[v])
 42         {
 43             child++;
 44             s.push(i);
 45             int lowv=dfs(v,id);
 46             lowu=min(lowv,lowu);
 47             if(lowv>=pre[u])  // 说明u是割顶
 48             {
 49                 iscut[u]=1;
 50                 bcc_cnt++;
 51                 bcc[bcc_cnt].clear();
 52                 for(;;)
 53                 {
 54                     Edge p=e[s.top()];
 55                     s.pop();
 56                     if(bccno[p.u]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.u);bccno[p.u]=bcc_cnt;}
 57                     if(bccno[p.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.v);bccno[p.v]=bcc_cnt;}
 58                     if(p.v==v&&p.u==u) break;
 59                 }
 60             }
 61         }
 62         else   if(pre[v]<pre[u])   //不加这一句就会错，，无解。。pre[v]难道不是一定小于pre[u]吗？？
 63         {
 64             s.push(i);
 65             lowu=min(lowu,pre[v]);
 66         }
 67     }
 68     if(id<0&&child==1) iscut[u]=0;
 69     return lowu;
 70 }
 71 
 72 void find_bcc(int n)
 73 {
 74     memset(pre,0,sizeof(pre));
 75     memset(bccno,0,sizeof(bccno));
 76     memset(iscut,0,sizeof(iscut));
 77     dfsk=bcc_cnt=0;
 78     for(int i=0;i<n;i++) if(!pre[i]) dfs(i,-1);
 79 }
 80 int odd[maxv],color[maxv];
 81 int bigraph(int u,int b)
 82 {
 83     for(int i=head[u];i!=-1;i=e[i].nex)
 84     {
 85         int v=e[i].v;
 86         if(bccno[v]!=b) continue;
 87         if(color[v]==color[u]) return 0;
 88         if(!color[v])
 89         {
 90             color[v]=3-color[u];
 91             if(!bigraph(v,b)) return 0;
 92         }
 93     }
 94     return 1;
 95 }
 96 int main()
 97 {
 98     while(scanf("%d%d",&n,&m)&&(n||m))
 99     {
100         init();
101         int u,v;
102         memset(A,0,sizeof(A));
103         for(int i=0;i<m;i++)
104         {
105             scanf("%d%d",&u,&v);
106             u--;v--;
107             A[u][v]=A[v][u]=1;
108         }
109         for(int i=0;i<n;i++)
110             for(int j=i+1;j<n;j++) if(!A[i][j])
111             {
112                 add(i,j);
113                 add(j,i);
114             }
115 
116         find_bcc(n);
117 
118         memset(odd,0,sizeof(odd));
119         for(int i=1;i<=bcc_cnt;i++)
120         {
121             memset(color,0,sizeof(color));
122             for(int j=0;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;  //有可能某个点属于多个环
123             int u=bcc[i][0];
124             color[u]=1;
125             if(!bigraph(u,i))  //不是二分图----有奇环----都可参加至少一次会议
126                 for(int j=0;j<bcc[i].size();j++) odd[bcc[i][j]]=1;
127         }
128         int ans=n;
129         for(int i=0;i<n;i++)
130             if(odd[i]) ans--;
131         printf("%d
",ans);
132     }
133 }

View Code

问题解决了，，pre[v]不一定小于pre[u],

在一个环里，如果顺时针dfs的话，最后会有pre[v]<pre[u],然后倒推回去会把这个环加到同一个新的联通分量里

接下来，按dfs接着走，会逆时针再去访问这个环，这时候会有pre[v]>pre[u],这种情况其实已经不能再把那条边压到栈里了，因为这个环已经记录过了，不用再处理

Mining Your Own Business

UVALive - 5135

无向图求割顶，，建图时总是忘记初始化。。。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define LL long long
  4 const int maxv=1010;
  5 const int maxe=100010;
  6 
  7 int n,m;
  8 struct Edge
  9 {
 10     int u,v,nex;
 11 }e[maxe];
 12 int head[maxe]; //
 13 int cnt=0;
 14 void init()
 15 {
 16     memset(head,-1,sizeof(head));
 17     cnt=0;
 18 }
 19 void add(int u,int v)
 20 {
 21     e[cnt].u=u;
 22     e[cnt].v=v;
 23     e[cnt].nex=head[u];
 24     head[u]=cnt++;
 25 }
 26 
 27 int pre[maxe],bccno[maxe],iscut[maxe],dfsk,bcc_cnt;
 28 vector<int> bcc[maxe]; //边双联通分量
 29 stack<int> s;  //边号
 30 int dfs(int u,int f)
 31 {
 32     int lowu=pre[u]=++dfsk;
 33     int child=0;
 34     for(int i=head[u];i!=-1;i=e[i].nex)
 35     {
 36         int v=e[i].v;
 37         if(!pre[v])
 38         {
 39             s.push(i);
 40             child++;
 41             int lowv=dfs(v,u);
 42             lowu=min(lowu,lowv);
 43             if(lowv>=pre[u])
 44             {
 45                 iscut[u]=1;
 46                 bcc_cnt++;
 47                 bcc[bcc_cnt].clear();
 48                 for(;;)
 49                 {
 50                     int te=s.top();
 51                     s.pop();
 52                     Edge p=e[te];
 53                     if(bccno[p.u]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.u); bccno[p.u]=bcc_cnt;}
 54                     if(bccno[p.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(p.v); bccno[p.v]=bcc_cnt;}
 55                     if(p.u==u&&p.v==v) break;
 56                 }
 57             }
 58         }
 59         else if(pre[v]<pre[u]&&v!=f)
 60         {
 61             s.push(i);
 62             lowu=min(pre[v],lowu);
 63         }
 64     }
 65     if(f<0&&child==1) iscut[u]=0;
 66     return lowu;
 67 }
 68 
 69 void find_bcc(int n)
 70 {
 71     memset(pre,0,sizeof(pre));
 72     memset(bccno,0,sizeof(bccno));
 73     memset(iscut,0,sizeof(iscut));
 74     dfsk=bcc_cnt=0;
 75     for(int i=0;i<n;i++) if(!pre[i])
 76         dfs(i,-1);
 77 }
 78 
 79 int main()
 80 {
 81     int kase=0;
 82    // freopen("in.txt","r",stdin);
 83     while(scanf("%d",&m)&&m)
 84     {
 85         n=0;
 86         init();
 87         int u,v;
 88         for(int i=0;i<m;i++)
 89         {
 90             scanf("%d%d",&u,&v);
 91             u--;v--;
 92             add(u,v);
 93             add(v,u);
 94             n=max(n,max(u,v));
 95         }
 96         find_bcc(n);
 97         LL ans1=0,ans2=1;
 98         for(int i=1;i<=bcc_cnt;i++)
 99         {
100             int cut_cnt=0;
101             for(int j=0;j<bcc[i].size();j++)
102                 if(iscut[bcc[i][j]]) cut_cnt++; //统计bcc中割顶数目
103             if(cut_cnt==1)
104             {
105                 ans1++;
106                 ans2*=(long long)(bcc[i].size()-1);
107             }
108         }
109         if(bcc_cnt==1)
110         {
111             ans1=2;
112             ans2=bcc[1].size()*(bcc[1].size()-1)/2;
113         }
114         printf("Case %d: %lld %lld
",++kase,ans1,ans2);
115     }
116 }

View Code

Proving Equivalences

UVALive - 4287

有向图，求双联通分量，然后再把每个联通分量缩成一个点

当每个点都有入有出时才成为双联通（不知道怎么描述，等想清楚了再回来写）

ans=max(a,b);

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxv=20010;
  4 const int maxe=50010;
  5 
  6 int n,m;
  7 
  8 struct Edge
  9 {
 10     int u,v,nex;
 11 }e[maxe<<1];
 12 int head[maxv];
 13 int cnt=0;
 14 void init()
 15 {
 16     memset(head,-1,sizeof(head));
 17     cnt=0;
 18 }
 19 void add(int u,int v)
 20 {
 21     e[cnt].u=u;
 22     e[cnt].v=v;
 23     e[cnt].nex=head[u];
 24     head[u]=cnt++;
 25 }
 26 
 27 int pre[maxv],sccno[maxv],lowlink[maxv],dfsk,scc_cnt;
 28 stack<int> s;
 29 
 30 void dfs(int u)
 31 {
 32     pre[u]=lowlink[u]=++dfsk;
 33     s.push(u);
 34     for(int i=head[u];i!=-1;i=e[i].nex)
 35     {
 36         int v=e[i].v;
 37         if(!pre[v])
 38         {
 39             dfs(v);
 40             lowlink[u]=min(lowlink[u],lowlink[v]);
 41         }
 42         else if(!sccno[v])
 43             lowlink[u]=min(lowlink[u],lowlink[v]);
 44     }
 45     if(lowlink[u]==pre[u])
 46     {
 47         scc_cnt++;
 48         for(;;)
 49         {
 50             int x=s.top();
 51             s.pop();
 52             sccno[x]=scc_cnt;
 53             if(x==u) break;
 54         }
 55     }
 56 }
 57 
 58 void find_scc(int n)
 59 {
 60     dfsk=scc_cnt=0;
 61     memset(sccno,0,sizeof(sccno));
 62     memset(pre,0,sizeof(pre));
 63     for(int i=0;i<n;i++) if(!pre[i])
 64         dfs(i);
 65 }
 66 int in0[maxv],out0[maxv];
 67 
 68 int main()
 69 {
 70     int t;
 71     scanf("%d",&t);
 72     while(t--)
 73     {
 74         init();
 75         scanf("%d%d",&n,&m);
 76         for(int i=0;i<m;i++)
 77         {
 78             int u,v;
 79             scanf("%d%d",&u,&v);
 80             u--;v--;
 81             add(u,v);
 82         }
 83 
 84         find_scc(n);
 85 
 86         for(int i=1;i<=scc_cnt;i++) in0[i]=out0[i]=1;
 87         for(int u=0;u<n;u++)
 88             for(int i=head[u];i!=-1;i=e[i].nex)
 89         {
 90             int v=e[i].v;
 91             if(sccno[v]!=sccno[u]) in0[sccno[v]]=out0[sccno[u]]=0;
 92         }
 93         int a=0,b=0;
 94         for(int i=1;i<=scc_cnt;i++)
 95         {
 96             if(in0[i]) a++;
 97             if(out0[i]) b++;
 98         }
 99         int ans=max(a,b);
100         if(scc_cnt==1) ans=0;
101         printf("%d
",ans);
102     }
103     return 0;
104 }

View Code

The Largest Clique

UVA - 11324

先求出SCC，然后缩点，就变成了一个DAG，每个点的权值为内点的个数，用DP求解最大值。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxv=1010;
 4 
 5 int n,m;
 6 
 7 vector<int> G[maxv];
 8 int pre[maxv],lowlink[maxv],sccno[maxv],dfsk,scc_cnt;
 9 stack<int> s;
10 
11 void dfs(int u)
12 {
13     pre[u]=lowlink[u]=++dfsk;
14     s.push(u);
15     for(int i=0;i<G[u].size();i++)
16     {
17         int v=G[u][i];
18         if(!pre[v])
19         {
20             dfs(v);
21             lowlink[u]=min(lowlink[u],lowlink[v]);
22         }
23         else if(!sccno[v]) lowlink[u]=min(lowlink[u],lowlink[v]);
24     }
25     if(lowlink[u]==pre[u])
26     {
27         scc_cnt++;
28         for(;;)
29         {
30             int x=s.top();
31             s.pop();
32             sccno[x]=scc_cnt;
33             if(x==u) break;
34         }
35     }
36 }
37 void find_scc(int n)
38 {
39     memset(pre,0,sizeof(pre));
40     memset(lowlink,0,sizeof(lowlink));
41     memset(sccno,0,sizeof(sccno));
42     dfsk=scc_cnt=0;
43     for(int i=0;i<n;i++) if(!pre[i])
44         dfs(i);
45 }
46 
47 int sz[maxv],d[maxv],TG[maxv][maxv];  //DP
48 int dp(int u)
49 {
50     if(d[u]>0) return d[u];
51     d[u]=sz[u];
52     for(int i=1;i<=scc_cnt;i++)
53         if(TG[u][i]&&u!=i) d[u]=max(d[u],dp(i)+sz[u]);
54     return d[u];
55 }
56 int main()
57 {
58     int t;
59     scanf("%d",&t);
60     while(t--)
61     {
62         scanf("%d%d",&n,&m);
63         for(int i=0;i<n;i++) G[i].clear();
64         int u,v;
65         for(int i=0;i<m;i++)
66         {
67             scanf("%d%d",&u,&v);
68             u--;v--;
69             G[u].push_back(v);
70         }
71         find_scc(n);
72 
73         //DP
74         memset(d,-1,sizeof(d));
75         memset(sz,0,sizeof(sz));
76         memset(TG,0,sizeof(TG));
77         for(int i=0;i<n;i++)
78         {
79             sz[sccno[i]]++;
80             for(int j=0;j<G[i].size();j++)
81             TG[sccno[i]][sccno[G[i][j]]]=1;
82         }
83         int ans=0;
84         for(int i=1;i<=scc_cnt;i++)
85             ans=max(ans,dp(i));
86         printf("%d
",ans);
87     }
88 }

COPY

Now or later

UVALive - 3211

2sat

第一次接触是大一刚开学不久的离散课上老师提到的，神奇orz

下面是lrj书上的模板

▄█▀█●

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2010;
 4 struct TwoSAT
 5 {
 6     int n;
 7     vector<int> G[maxn<<1];
 8     bool mark[maxn<<1];
 9     int s[maxn<<1],c;
10 
11     bool dfs(int x)
12     {
13         if(mark[x^1]) return false;
14         if(mark[x]) return true;
15         mark[x]=true;
16         s[c++]=x;
17         for(int i=0;i<G[x].size();i++)
18             if(!dfs(G[x][i])) return false;
19         return true;
20     }
21 
22     void init(int n)
23     {
24         this->n=n;
25         for(int i=0;i<n*2;i++) G[i].clear();
26         memset(mark,0,sizeof(mark));
27     }
28 
29     void add_clause(int x,int xv,int y,int yv)
30     {
31         x=x*2+xv;
32         y=y*2+yv;
33         G[x^1].push_back(y);
34         G[y^1].push_back(x);
35     }
36 
37     bool solve()
38     {
39         for(int i=0;i<n*2;i+=2)
40             if(!mark[i]&&!mark[i^1])
41             {
42                 c=0;
43                 if(!dfs(i))
44                 {
45                     while(c>0) mark[s[--c]]=false;
46                     if(!dfs(i+1)) return false;
47                 }
48             }
49         return true;
50     }
51 }solver;
52 int n;
53 int T[maxn][2];
54 
55 bool test(int diff)
56 {
57     solver.init(n);
58     for(int i=0;i<n;i++) for(int a=0;a<2;a++)
59         for(int j=i+1;j<n;j++) for(int b=0;b<2;b++)
60         if(abs(T[i][a]-T[j][b])<diff) solver.add_clause(i,a^1,j,b^1);
61     return solver.solve();
62 }
63 
64 int main()
65 {
66     while(scanf("%d",&n)==1&&n)
67     {
68         int L=0,R=0;
69         for(int i=0;i<n;i++) for(int a=0;a<2;a++)
70         {
71             scanf("%d",&T[i][a]);
72             R=max(R,T[i][a]);
73         }
74         while(L<R)
75         {
76             int M=(R-L+1)/2+L;
77             if(test(M)) L=M;
78             else R=M-1;
79         }
80         printf("%d
",L);
81     }
82     return 0;
83 
84 
85 }

LRJ

Astronauts

UVALive - 3713

还是2sat，，模板好用啊 ▄█▀█●

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=100010;
 4 struct TwoSAT
 5 {
 6     int n;
 7     vector<int> G[maxn<<1];
 8     bool mark[maxn<<1];
 9     int s[maxn<<1],c;
10 
11     bool dfs(int x)
12     {
13         if(mark[x^1]) return false;
14         if(mark[x]) return true;
15         mark[x]=true;
16         s[c++]=x;
17         for(int i=0;i<G[x].size();i++)
18             if(!dfs(G[x][i])) return false;
19         return true;
20     }
21 
22     void init(int n)
23     {
24         this->n=n;
25         for(int i=0;i<n*2;i++) G[i].clear();
26         memset(mark,0,sizeof(mark));
27     }
28 
29     void add_clause(int x,int xv,int y,int yv)
30     {
31         x=x*2+xv;
32         y=y*2+yv;
33         G[x^1].push_back(y);
34         G[y^1].push_back(x);
35     }
36 
37     bool solve()
38     {
39         for(int i=0;i<n*2;i+=2)
40             if(!mark[i]&&!mark[i^1])
41             {
42                 c=0;
43                 if(!dfs(i))
44                 {
45                     while(c>0) mark[s[--c]]=false;
46                     if(!dfs(i+1)) return false;
47                 }
48             }
49         return true;
50     }
51 }solver;
52 int n,m;
53 int age[maxn],sum;
54 
55 bool check(int x)
56 {
57     return age[x]*n<sum;
58 }
59 
60 int main()
61 {
62     while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
63     {
64         sum=0;
65         for(int i=0;i<n;i++) {
66             scanf("%d",&age[i]);
67             sum+=age[i];
68         }
69         solver.init(n);
70         for(int i=0;i<m;i++)
71         {
72             int a,b;
73             scanf("%d%d",&a,&b);
74             a--;b--;
75             solver.add_clause(a,1,b,1);
76             if(check(a)==check(b)) solver.add_clause(a,0,b,0);
77         }
78         if(!solver.solve()) printf("No solution
");
79         else {
80             for(int i=0;i<n;i++)
81             if(solver.mark[i*2]) printf("C
");
82             else if(check(i)) puts("B");
83             else puts("A");
84         }
85     }
86     return 0;
87 
88 
89 }

View Code

最短路：

Airport Express

UVA - 11374

怎么说呢，，看了一个人的代码，里面有一点小错误，搞了很久才发现，这种人太不负责任了，贴代码也要有原则的吧=_=||

算是对输出路径有了更深的理解

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int inf=0x3f3f3f3f;
  4 const int maxv=1010;
  5 const int maxe=1010;
  6 
  7 struct Edge
  8 {
  9     int u,v,w;
 10     int nex;
 11 }e[maxe<<1];
 12 int head[maxv];
 13 int cnt=0;
 14 void init()
 15 {
 16     memset(head,-1,sizeof(head));
 17     cnt=0;
 18 }
 19 void add(int u,int v,int w)
 20 {
 21     e[cnt].u=u;
 22     e[cnt].v=v;
 23     e[cnt].w=w;
 24     e[cnt].nex=head[u];
 25     head[u]=cnt++;
 26 }
 27 
 28 typedef pair<int,int> PII;
 29 int dis[maxv];
 30 int par[maxv];
 31 void dijkstra(int s)
 32 {
 33     priority_queue<PII,vector<PII>,greater<PII> > pq;
 34     for(int i=0;i<maxv;i++) dis[i]=inf;
 35     dis[s]=0;
 36     pq.push(PII(0,s));
 37     while(!pq.empty())
 38     {
 39         PII temp=pq.top();
 40         pq.pop();
 41         int u=temp.second;
 42         if(dis[u]<temp.first) continue;
 43         for(int i=head[u];i!=-1;i=e[i].nex)
 44         {
 45             if(dis[e[i].v]>dis[u]+e[i].w)
 46             {
 47                 dis[e[i].v]=dis[u]+e[i].w;
 48                 par[e[i].v]=i;
 49                 pq.push(PII(dis[e[i].v],e[i].v));
 50             }
 51         }
 52     }
 53 }
 54 int n,ss,ee;
 55 int ds[maxv],de[maxv];
 56 int p[maxv],p1[maxv];
 57 
 58 void print(int a)
 59 {
 60     if(a==ss)
 61     {
 62         printf("%d",a+1);
 63     }
 64     else
 65     {
 66         int x=p1[a];
 67         print(e[x].u);
 68         printf(" %d",a+1);
 69     }
 70     return ;
 71 }
 72 
 73 int main()
 74 {
 75     int kase=0;
 76 
 77     while(scanf("%d%d%d",&n,&ss,&ee)!=EOF&&n)
 78     {
 79         if(kase++) puts("");
 80         ss--;ee--;
 81         init();
 82         int u,v,w;
 83         int m;
 84         scanf("%d",&m);
 85         for(int i=0;i<m;i++)
 86         {
 87             scanf("%d%d%d",&u,&v,&w);
 88             u--,v--;
 89             add(u,v,w);
 90             add(v,u,w);
 91         }
 92         dijkstra(ss);
 93         for(int i=0;i<n;i++) {ds[i]=dis[i];p1[i]=par[i];}
 94         pa[ss]=-1;
 95         dijkstra(ee);
 96         for(int i=0;i<n;i++) {de[i]=dis[i];p[i]=par[i];}
 97         p[ee]=-1;
 98 
 99 
100         int ans1=ds[ee];
101         int a=-1,b=-1;
102         int k;
103         scanf("%d",&k);
104         for(int i=0;i<k;i++)
105         {
106             scanf("%d%d%d",&u,&v,&w);
107             u--;v--;
108             if(ans1>ds[u]+w+de[v])
109             {
110                 ans1=ds[u]+w+de[v];
111                 a=u,b=v;
112             }
113             if(ans1>ds[v]+w+de[u])
114             {
115                 ans1=ds[v]+w+de[u];
116                 a=v,b=u;
117             }
118         }
119 
120         int flag=0;
121         if(a==-1)
122         {
123             int x=ss;
124             while(x!=ee)
125             {
126                 if(!flag){printf("%d",x+1);flag=1;}
127                 else printf(" %d",x+1);
128                 x=e[p[x]].u;
129             }
130             printf(" %d
",ee+1);
131             printf("Ticket Not Used
%d
",ans1);
132         }
133         else
134         {
135             print(a);
136             int x=b;
137             while(x!=ee)
138             {
139                 printf(" %d",x+1);
140                 x=e[p[x]].u;
141             }
142             printf(" %d
",ee+1);
143             printf("%d
%d
",a+1,ans1);
144         }
145     }
146     return 0;
147 }

View Code

Walk Through the Forest

UVA - 10917

最短路树，DP求解

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int inf=0x3f3f3f3f;
 4 const int maxv=1010;
 5 const int maxe=1000010; //??
 6 int n,m;
 7 struct Edge
 8 {
 9     int u,v,w;
10     int nex;
11 }e[maxe<<1];
12 int head[maxv];
13 int cnt=0;
14 void init()
15 {
16     memset(head,-1,sizeof(head));
17     cnt=0;
18 }
19 void add(int u,int v,int w)
20 {
21     e[cnt].u=u;
22     e[cnt].v=v;
23     e[cnt].w=w;
24     e[cnt].nex=head[u];
25     head[u]=cnt++;
26 }
27 typedef pair<int,int> PII;
28 int dis[maxv],par[maxv];
29 void dijkstra(int s)
30 {
31     priority_queue<PII,vector<PII>,greater<PII> > pq;
32     for(int i=0;i<maxv;i++) dis[i]=inf;
33     dis[s]=0;
34     pq.push(PII(0,s));
35     while(!pq.empty())
36     {
37         PII temp=pq.top();
38         pq.pop();
39         int u=temp.second;
40         if(dis[u]<temp.first) continue;
41         for(int i=head[u];i!=-1;i=e[i].nex)
42         {
43             int v=e[i].v;
44             if(dis[v]>dis[u]+e[i].w)
45             {
46                 dis[v]=dis[u]+e[i].w;
47                 par[v]=i;
48                 pq.push(PII(dis[v],v));
49             }
50         }
51     }
52 }
53 int dp[maxv];
54 int DP(int u)
55 {
56     if(u==1) return 1;
57     if(dp[u]!=-1) return dp[u];
58     dp[u]=0;
59     for(int i=head[u];i!=-1;i=e[i].nex)
60     {
61         int v=e[i].v;
62         if(dis[v]<dis[u]) dp[u]+=DP(v);
63     }
64     return dp[u];
65 }
66 int main()
67 {
68     while(scanf("%d",&n)&&n)
69     {
70         scanf("%d",&m);
71         init();
72         int u,v,w;
73         for(int i=0;i<m;i++)
74         {
75             scanf("%d%d%d",&u,&v,&w);
76             u--;v--;
77             add(u,v,w);
78             add(v,u,w);
79         }
80         dijkstra(1);
81         memset(dp,-1,sizeof(dp));
82         int ans=DP(0);
83         printf("%d
",ans);
84     }
85 
86 }

View Code

Warfare And Logistics

UVALive - 4080

怎么今天总是踩到各种坑里=_=||

没有原题，，lrj书上说1000条边，可是我开到1000各种WA了n次

别人也是1000就过了orz。。我得开到2000才能过

无解，，看不出来代码哪里有问题

【如果每次删除一条边，要跑m次dijkstra，其实其中很多次都对最短路没有影响，因为删掉的边不在最短路里】

【因此，可以每次删除最短路树中的一条边，需要跑n次，复杂度降低到可接受程度】

再补充一点补码的知识，上学期学过可是已经忘了，刚刚翻得书=_=||

正数的补码简单，直接写成二进制形式即可

对于负数，先写出对应的正数的补码，然后右边起到第一位不是0的这些位不变，其它位取反，即是负数的补码

比如 -3的补码为 0000 0011——》1111 1101

　　所以-3取反之后就变成了0000 0010，即2

在用前向星存边时，从0开始，那么i与i^1是一对边，i是正向，i^1是反向

如果要求某条边i的正向边怎么求呢？只需要（i&（-2））即得到正向边

因为-2的补码为11111110，（i&（-2））即把最右那位置0，其它位不变，得到的就是正向边了

  1 #include <bits/stdc++.h>
  2 #define LL long long
  3 using namespace std;
  4 const int inf=0x3f3f3f3f;
  5 const int maxv=110;
  6 const int maxe=2010;
  7 int n,m,L;
  8 struct Edge
  9 {
 10     int u,v,w;
 11     int nex;
 12 }e[maxe<<1];
 13 int head[maxv];
 14 int cnt=0;
 15 void init()
 16 {
 17     memset(head,-1,sizeof(head));
 18     cnt=0;
 19 }
 20 void add(int u,int v,int w)
 21 {
 22     e[cnt].u=u;
 23     e[cnt].v=v;
 24     e[cnt].w=w;
 25     e[cnt].nex=head[u];
 26     head[u]=cnt++;
 27 }
 28 
 29 typedef pair<int,int> PII;
 30 int dis[maxv],par[maxv];
 31 void dijkstra(int s,bool c,int e1)
 32 {
 33     priority_queue<PII,vector<PII>,greater<PII> > pq;
 34     for(int i=0;i<maxv;i++) dis[i]=L;
 35     dis[s]=0;
 36     pq.push(PII(0,s));
 37     par[s]=-1;
 38     while(!pq.empty())
 39     {
 40         PII t=pq.top();
 41         pq.pop();
 42         int u=t.second;
 43         if(dis[u]<t.first) continue;
 44         for(int i=head[u];i!=-1;i=e[i].nex)
 45         {
 46             if(i==e1||i==(e1^1)) continue;   //
 47             int v=e[i].v;
 48             if(dis[v]>dis[u]+e[i].w)
 49             {
 50                 dis[v]=dis[u]+e[i].w;
 51                 if(c) par[v]=i;
 52                 pq.push(PII(dis[v],v));
 53             }
 54         }
 55     }
 56 }
 57 LL cal()
 58 {
 59     LL temp=0;
 60     for(int i=0;i<n;i++)
 61         temp+=dis[i];
 62     return temp;
 63 }
 64 vector<int> vv;
 65 int delta[maxe];
 66 
 67 int main()
 68 {
 69     while(scanf("%d%d%d",&n,&m,&L)!=EOF)
 70     {
 71         init();
 72         int u,v,w;
 73         for(int i=0;i<m;i++)
 74         {
 75             scanf("%d%d%d",&u,&v,&w);
 76             u--;v--;
 77             add(u,v,w);
 78             add(v,u,w);
 79         }
 80         LL ans=0;
 81         vv.clear();
 82         memset(delta,0,sizeof(delta));
 83         for(int i=0;i<n;i++)
 84         {
 85             dijkstra(i,1,-1);
 86             LL temp=cal();
 87             ans+=temp;
 88             for(int j=0;j<n;j++)
 89                 if(par[j]!=-1)
 90             {
 91                 dijkstra(i,0,par[j]);
 92                 int id=par[j]&(~1);   //
 93                 if(!delta[id]) vv.push_back(id);
 94                 delta[id]+=cal()-temp;
 95             }
 96 
 97         }
 98         int maxdelta=0;
 99         for(int i=0;i<(int)vv.size();i++)
100             maxdelta=max(maxdelta,delta[vv[i]]);
101         printf("%lld %lld
",ans,ans+maxdelta);
102     }
103 }

View Code

附上大佬代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 102, maxm = 2002;
 5 int head[maxn], to[maxm], nxt[maxm],wei[maxm],ecnt;
 6 int delta[maxm];
 7 
 8 void addEdge(int u,int v,int w)
 9 {
10     to[ecnt] = v;
11     nxt[ecnt] = head[u];
12     wei[ecnt] = w;
13     head[u] = ecnt++;
14 }
15 
16 typedef pair<int,int> Node;
17 #define fi first
18 #define se second
19 
20 int d[maxn],pa[maxn];
21 typedef long long ll;
22 
23 void dijkstra(int n,int s,int L,bool flag,int e1,int e2)// e1 e2 边应该忽略
24 {
25     priority_queue<Node,vector<Node>,greater<Node> > q;
26     fill(d,d+n,L);
27     d[s] = 0; q.push(Node(0,s)); pa[s] = -1;
28     while(q.size()){
29         Node x = q.top(); q.pop();
30         int u = x.se;
31         if(x.fi != d[u]) continue;
32         for(int i = head[u]; ~i; i = nxt[i])if(i!=e1 && i!=e2) {
33             int v = to[i];
34             if(d[v] > d[u]+wei[i]){
35                 d[v] = d[u]+wei[i];
36                 if(flag) pa[v] = i; // 入边编号
37                 q.push(Node(d[v],v));
38             }
39         }
40     }
41 }
42 
43 ll cal(int n)
44 {
45     ll ret = 0;
46     for(int i = 0; i < n; i++){
47         ret += d[i];
48     }
49     return ret;
50 }
51 
52 
53 void init()
54 {
55     memset(head,-1,sizeof(head));
56     ecnt = 0;
57     memset(delta,0,sizeof(delta));
58 }
59 
60 int main()
61 {
62     //freopen("in.txt","r",stdin);
63     int n,m,L;
64     while(~scanf("%d%d%d",&n,&m,&L)){
65         init();
66          while(m--){
67             int u,v,w; scanf("%d%d%d",&u,&v,&w);
68             addEdge(--u,--v,w); addEdge(v,u,w);
69         }
70         ll ans1 = 0;
71         vector<int> edges;
72         for(int u = 0; u < n; u++){
73             dijkstra(n,u,L,true,-1,-1);
74             ll t  = cal(n);
75             ans1 += t;
76             for(int i = 0; i < n; i++){
77                 if(~pa[i]){
78                     dijkstra(n,u,L,false,pa[i],pa[i]^1);
79                     int eid = pa[i]&(~1);
80                     if(!delta[eid]) edges.push_back(eid);
81                     delta[eid] += cal(n)-t;
82                 }
83             }
84         }
85         int MaxDelta = 0;
86         for(int i = 0; i < (int)edges.size(); i++){
87             MaxDelta = max(MaxDelta,delta[edges[i]]);
88         }
89         printf("%lld %lld
",ans1,ans1+MaxDelta);
90     }
91     return 0;
92 }

View Code

The Toll! Revisited

UVA - 10537

不想做了，，先贴上LRJ代码，日后再做

 1 // UVa10537 Toll! Revisited
 2 // Rujia Liu
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 52 + 10;
 9 const long long INF = 1LL << 60;
10 typedef long long LL;
11 
12 int n, G[maxn][maxn], src, dest, p;
13 int mark[maxn]; // 标记
14 LL d[maxn];     // d[i]表示从点i出发（已经交过点i的税了）时至少要带多少东西，到dest时还能剩p个东西
15 
16 int read_node() {
17   char ch[9];
18   scanf("%s", ch);
19   if(ch[0] >= 'A' && ch[0] <= 'Z') return ch[0] - 'A';
20   else return ch[0] - 'a' + 26;
21 }
22 
23 char format_node(int u) {
24   return u < 26 ? 'A' + u : 'a' + (u - 26);
25 }
26 
27 // 拿着item个东西去结点next，还剩多少个东西
28 LL forward(LL item, int next) {
29   if(next < 26) return item - (item + 19) / 20;
30   return item - 1;
31 }
32 
33 // 至少要拿着多少个东西到达结点u，交税以后还能剩d[u]个东西
34 // 为了使代码容易理解，这里使用一种不太数学的解法
35 LL back(int u) {
36   if(u >= 26) return d[u]+1;
37   LL X = d[u] * 20 / 19; // 初始值
38   while(forward(X, u) < d[u]) X++; // 调整
39   return X;
40 }
41 
42 void solve() {
43   n = 52; // 总是有52个结点
44   memset(mark, 0, sizeof(mark));
45   d[dest] = p;
46   mark[dest] = 1;
47   for(int i = 0; i < n; i++) if(i != dest) {
48     d[i] = INF;
49     if(G[i][dest]) d[i] = back(dest);
50   }
51 
52   // Dijkstra主过程，逆推
53   while(!mark[src]) {
54     // 找最小的d
55     int minu = -1;
56     for(int i = 0; i < n; i++) if(!mark[i]) {
57       if(minu < 0 || d[i] < d[minu]) minu = i;
58     }
59     mark[minu] = 1;
60     // 更新其他结点的d
61     for(int i = 0; i < n; i++) if(!mark[i]) {
62       if(G[i][minu]) d[i] = min(d[i], back(minu));
63     }
64   }
65 
66   // 输出
67   printf("%lld
", d[src]);
68   printf("%c", format_node(src));
69   int u = src;
70   LL item = d[src];
71   while(u != dest) {
72     int next;
73     for(next = 0; next < n; next++) // 找到第一个可以走的结点
74       if(G[u][next] && forward(item, next) >= d[next]) break;
75     item = d[next];
76     printf("-%c", format_node(next));
77     u = next;
78   }
79   printf("
");
80 }
81 
82 int main() {
83   int kase = 0;
84   while(scanf("%d", &n) == 1 && n >= 0) {
85     memset(G, 0, sizeof(G));
86     for(int i = 0; i < n; i++) {
87       int u = read_node();
88       int v = read_node();
89       if(u != v) G[u][v] = G[v][u] = 1;
90     }
91     scanf("%d", &p);
92     src = read_node();
93     dest = read_node();
94     printf("Case %d:
", ++kase);
95     solve();
96   }
97   return 0;
98 }

LRJ

Halum

UVA - 11478

差分约束

简直要崩溃了，，无法理解。。。。。。

事实证明是书上写错了，不是非负，而是要求必须大于0.

忧伤=_=||

 1 // UVa11478 Halum
 2 // Rujia Liu
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 
 8 const int INF = 1000000000;
 9 const int maxn = 500 + 10;
10 const int maxm = 2700 + 10;
11 
12 struct Edge {
13   int to, dist;
14 };
15 
16 // 邻接表写法
17 struct BellmanFord {
18   int n, m;
19   Edge edges[maxm];
20   int head[maxn];
21   int next[maxm];
22   bool inq[maxn];   // 是否在队列中
23   int d[maxn];      // s到各个点的距离
24   int cnt[maxn];    // 进队次数
25 
26   void init(int n) {
27     this->n = n;
28     m = 0;
29     memset(head, -1, sizeof(head));
30   }
31 
32   void AddEdge(int from, int to, int dist) {
33     next[m] = head[from];
34     head[from] = m;
35     edges[m++] = (Edge){to, dist};
36   }
37 
38   bool negativeCycle() {
39     queue<int> Q;
40     memset(inq, 0, sizeof(inq));
41     memset(cnt, 0, sizeof(cnt));
42     for(int i = 0; i < n; i++) { d[i] = 0; Q.push(i); }
43 
44     int u;
45     while(!Q.empty()) {
46       u = Q.front(); Q.pop();
47       inq[u] = false;
48       for(int i = head[u]; i != -1; i = next[i]) {
49         Edge& e = edges[i];
50         if(d[e.to] > d[u] + e.dist) {
51           d[e.to] = d[u] + e.dist;
52           if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
53         }
54       }
55     }
56     return false;
57   }
58 };
59 
60 BellmanFord solver;
61 
62 // 判断在初始差分约束系统的每个不等式右侧同时减去x之后是否有解
63 bool test(int x) {
64   for(int i = 0; i < solver.m; i++)
65     solver.edges[i].dist -= x;
66   bool ret = solver.negativeCycle();
67   for(int i = 0; i < solver.m; i++)
68     solver.edges[i].dist += x;
69   return !ret; // 如果有负环，说明差分约束系统无解
70 }
71 
72 int main() {
73   int n, m;
74   while(scanf("%d%d", &n, &m) == 2) {
75     solver.init(n);
76     int ub = 0;
77     while(m--) {
78       int u, v, d;
79       scanf("%d%d%d", &u, &v, &d); ub = max(ub, d);
80       solver.AddEdge(u-1, v-1, d);
81     }
82 
83     if(test(ub+1)) printf("Infinite
"); // 如果可以让每条边权都>ub，说明每条边的权都增加了，重复一次会增加得更多...直到无限
84     else if(!test(1)) printf("No Solution
");
85     else {
86       int L = 2, R = ub, ans = 1;
87       while(L <= R) {
88         int M = L + (R-L)/2;
89         if(test(M)) { ans = M; L = M+1; } else R = M-1;
90       }
91       printf("%d
", ans);
92     }
93   }
94   return 0;
95 }