Diposting di | Edited on

Taxi Cab Scheme

UVALive - 3126

题目大意：n个客人，从城市的不同位置出发，到达他们的目的地。已知每个人的出发时间hh：mm，出发地点（x1，y1）及目的地（x2，y2），要求使用最少的出租车接送乘客，使得每个顾客的要求都被执行，且每次出租车接客时需要至少提前一分钟到达乘客所在的位置。城区是网格型的，地址用（x，y）表示，出租车从（x1，y1）到（x2，y2）需要行驶|x1 - x2| + |y1 - y2|分钟。

题目分析：本题的模型是DAG上的最小路径覆盖。将每个客人视为一个节点，如果接送完顾客i后还可以继续接送顾客j，则对应DAG中的一条边i -> j。对每个节点拆点为i，i’，如果图中存在有向边i -> j，则建边（i，j’）。设二分图的最大匹配数为m，则结果即为n - m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"bbibibibbbb="<<endl;
/// 二分图最大基数匹配
struct BPM{
    int n,m;    /// 左右顶点个数
    int G[maxn][maxn]; /// 邻接表
    int left[maxn];    /// left[i]为右边第i个点的匹配点编号，-1表示不存在
    bool T[maxn];       /// T[i]为右边第i个点是否已标记

    int right[maxn];        /// 求最小覆盖用
    bool S[maxn];           /// 求最小覆盖用

    void init(int n,int m){
        this->n=n;
        this->m=m;
        memset(G,0,sizeof(G));
    }

   /* void AddEdge(int u,int v){
        G[u].push_back(v);
    }*/

    bool match(int u){
        S[u]=true;
        for(int v=0;v<m;v++){
            //int v=G[u][i];
            if(G[u][v]&&!T[v]){
                T[v]=true;
                if(left[v]==-1||match(left[v])){
                    left[v]=u;
                    right[u]=v;
                    return true;
                }
            }
        }
        return false;
    }
    /// 求最大匹配
    int solve(){
        memset(left,-1,sizeof(left));
        memset(right,-1,sizeof(right));
        int ans=0;
        for(int u=0;u<n;u++){
            memset(S,0,sizeof(S));
            memset(T,0,sizeof(T));
            if(match(u))ans++;
        }
        return ans;
    }
    /// 求最小覆盖。X和Y为最小覆盖中的点集
    int mincover(vector<int>& X,vector<int>& Y){
        int ans=solve();
        memset(S,0,sizeof(S));
        memset(T,0,sizeof(T));
        for(int u=0;u<n;u++)
            if(right[u]==-1)match(u);
        for(int u=0;u<n;u++)
            if(!S[u])X.push_back(u);
        for(int v=0;v<n;v++)
            if(T[v])Y.push_back(v);
        return ans;
    }
};
BPM solver;
int x1[maxn],yyy[maxn],x2[maxn],y2[maxn],t1[maxn],t2[maxn];
int dist(int a,int b,int c,int d){
    return abs(a-c)+abs(b-d);
}

int main(){
  int T;
  scanf("%d", &T);
  while(T--) {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
      int h, m;
      scanf("%d:%d%d%d%d%d", &h, &m, &x1[i], &yyy[i], &x2[i], &y2[i]);
      t1[i] = h*60+m;
      t2[i] = t1[i] + dist(x1[i], yyy[i], x2[i], y2[i]);
    }
    solver.init(n, n);
    for(int i = 0; i < n; i++)
      for(int j = i+1; j < n; j++)
        if(t2[i] + dist(x2[i], y2[i], x1[j], yyy[j]) < t1[j]) solver.G[i][j] = 1; // 至少要提前1分钟到达
    printf("%d\n", n - solver.solve());
  }
  return 0;
}

Diposting di | Edited on

Stream My Contest

UVA - 11865

二分带宽，然后判断最小生成树是否小于cost值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=100+50;
const ll inf=1000000000;;

/// 固定根的最小树型图，邻接矩阵写法
struct MDST{
    int n;
    int w[maxn][maxn];    ///边权
    int vis[maxn];        ///访问标记，仅用来判断无解
    int ans;              ///计算答案
    int removed[maxn];    ///每个点是否被删除
    int cid[maxn];        ///所在圈编号
    int pre[maxn];        ///最小入边的起点
    int iw[maxn];         ///最小入边的权值
    int max_cid;          ///最大圈编号

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)w[i][j]=inf;
    }
    void AddEdge(int u,int v,int cost){
        w[u][v]=min(w[u][v],cost);  ///重边取权值最小的
    }

    ///从s出发能到达多少个结点
    int dfs(int s){
        int ans=1;
        vis[s]=1;
        for(int i=0;i<n;i++)if(!vis[i]&&w[s][i]<inf)ans+=dfs(i);
        return ans;
    }
    ///从u出发沿着pre指针找圈
    bool cycle(int u){
        max_cid++;
        int v=u;
        while(cid[v]!=max_cid){cid[v]=max_cid;v=pre[v];}
        return v==u;
    }
    /// 计算u的最小入弧，入弧起点不得在圈c中
    void update(int u){
        iw[u]=inf;
        for(int i=0;i<n;i++)
        if(!removed[i]&&w[i][u]<iw[u]){
            iw[u]=w[i][u];
            pre[u]=i;
        }
    }
    ///根节点为s,如果失败返回false
    bool solve(int s){
        memset(vis,0,sizeof(vis));
        if(dfs(s)!=n)return false;
        memset(removed,0,sizeof(removed));
        memset(cid,0,sizeof(cid));
        for(int u=0;u<n;u++)update(u);
        pre[s]=s;iw[s]=0;      /// 根结点特殊处理
        ans=max_cid=0;
        for(;;){
            bool have_cycle=false;
            for(int u=0;u<n;u++)if(u!=s&&!removed[u]&&cycle(u)){
                have_cycle=true;
                /// 以下代码缩圈，圈上除了u之外的结点均删除
                int v=u;
                do{
                    if(v!=u)removed[v]=1;
                    ans+=iw[v];
                    /// 对于圈外点i，把边i->v改成i->u（并调整权值）；v->i改为u->i
                    /// 注意圈上可能还有一个v'使得i->v'或者v'->i存在，因此只保留权值最小的i->u和u->i
                    for(int i=0;i<n;i++)if(cid[i]!=cid[u]&&!removed[i]){
                        if(w[i][v]<inf)w[i][u]=min(w[i][u],w[i][v]-iw[v]);
                        w[u][i]=min(w[u][i],w[v][i]);
                        if(pre[i]==v)pre[i]=u;
                    }
                    v=pre[v];
                }while(v!=u);
                update(u);
                break;
            }
            if(!have_cycle)break;
        }
        for(int i=0;i<n;i++)
            if(!removed[i])ans+=iw[i];
        return true;
    }
};
MDST solver;
struct Edge{
    int u,v,b,c;
    bool operator <(const Edge& rhs)const{
        return b>rhs.b;
    }
};
const int maxm=10000+10;
int n,m,C;
Edge edges[maxm];
bool check(int cnt){
    solver.init(n);
    for(int i=0;i<cnt;i++)
        solver.AddEdge(edges[i].u,edges[i].v,edges[i].c);
    if(!solver.solve(0))return false;
    return solver.ans<=C;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
  /*  int a=inf;
    cout<<a<<endl<<1000000000<<endl;*/
    cin>>t;
    while(t--){
        cin>>n>>m>>C;
        for(int i=0;i<m;i++)cin>>edges[i].u>>edges[i].v>>edges[i].b>>edges[i].c;
        sort(edges,edges+m);
        int l=1,r=m,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){ans=edges[mid-1].b;r=mid-1;}
            else l=mid+1;
        }
        if(ans<0)cout<<"streaming not possible."<<endl;
        else cout<<ans<<" kbps"<<endl;
    }
    return 0;
}

Diposting di | Edited on

Halum

UVA - 11478

题意

带权有向图，每个点都可以有如下操作：令从ta出发的每一条边增加d，终止于ta的每一条边减小d
最后让所有边权的最小值非负且尽量大

题解

考虑每条边的约束，di表示i的halum量

w-dv+du>0

dv-du<w

但求解这个差分约束系统只是让这组不等式成立，最长路和最短路控制的都是单个d的最值而不是最小值最大

那如何最小值最大呢？

二分答案……

那么不等式变为dv-du<w-mid，成立的话说明经过操作后边权可以都比mid大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2700+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge
{
    int from, to;
    int dist;
    Edge() {}
    Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
};
struct BellmanFord{
    int n,m;
    vector<Edge>edges;
    vector<int> G[maxn];
    bool inq[maxn]; /// 是否在队列中
    int d[maxn];    /// s到各个点的距离  double 要改成double类型
    int p[maxn];    /// 最短路中的上一条弧
    int cnt[maxn];  /// 进队次数
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(from, to, dist);
        m = edges.size();
        G[from].push_back(m - 1);
    }
    bool bellmanford(int s){
        queue<int>Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } ///如果只判负环用这个
        //for(int i=0;i<n;i++)d[i]=inf;
        //d[s]=0;inq[s]=true;Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=false;
            for(auto& id:G[u]){
                Edge& e=edges[id];
                if(d[u]<inf && d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u] + e.dist;
                    p[e.to]=id;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)return true;
                    }
                }
            }
        }
        return false;
    }
};
BellmanFord solver;
bool test(int x){
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist-=x;
    bool ret=solver.bellmanford(0);
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist+=x;
    return !ret;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        solver.init(n);
        int ub=0;
        while(m--){
            int u,v,d;
            cin>>u>>v>>d;ub=max(ub,d);
            solver.AddEdge(u-1,v-1,d);
        }
        if(test(ub+1))cout<<"Infinite"<<endl;
        else if(!test(1))cout<<"No Solution"<<endl;
        else{
            int l=2,r=ub,ans=1;
            while(l<=r){
                int mid=(l+r)/2;
                if(test(mid)){ans=mid;l=mid+1;}
                else r=mid-1;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Diposting di | Edited on

SAM I AM

UVA - 11419

题目大意：给出一个R×C的网格，网格上棉纺了一些目标。可以在网格外发射子弹，子弹会沿着垂直或水平方向飞行，并且打掉飞行路径上的所有目标。你的任务是计算出最少需要多少子弹，各从哪个位置发射，才能把所有目标全部打掉。
解题思路：König定理：最小覆盖数等于最大匹配数。把目标所在的坐标，转化为XY结点，行看成X结点，列看成Y结点。那现在问题就变成了，如何选最少的结点，覆盖所有的边。

求最小覆盖的步骤大致如下：1）在右边找到一个未被匹配过的点，标记。2）走一条没被匹配过的边，到左边的点，标记。3）走一条匹配过的边到右边，标记。4）重复2,3步骤直到不能再走。5）回到步骤一，直到找不到未被匹配且未被标记的右边的点。6）标记结束后，右边没有标记的点，和左边标记过的点，就可以覆盖所有的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"bbibibibbbb="<<endl;
/// 二分图最大基数匹配
struct BPM{
    int n,m;    /// 左右顶点个数
    vector<int>G[maxn]; /// 邻接表
    int left[maxn];    /// left[i]为右边第i个点的匹配点编号，-1表示不存在
    bool T[maxn];       /// T[i]为右边第i个点是否已标记

    int right[maxn];        /// 求最小覆盖用
    bool S[maxn];           /// 求最小覆盖用

    void init(int n,int m){
        this->n=n;
        this->m=m;
        for(int i=0;i<n;i++)G[i].clear();
    }

    void AddEdge(int u,int v){
        G[u].push_back(v);
    }

    bool match(int u){
        S[u]=true;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(!T[v]){
                T[v]=true;
                if(left[v]==-1||match(left[v])){
                    left[v]=u;
                    right[u]=v;
                    return true;
                }
            }
        }
        return false;
    }
    /// 求最大匹配
    int solve(){
        memset(left,-1,sizeof(left));
        memset(right,-1,sizeof(right));
        int ans=0;
        for(int u=0;u<n;u++){
            memset(S,0,sizeof(S));
            memset(T,0,sizeof(T));
            if(match(u))ans++;
        }
        return ans;
    }
    /// 求最小覆盖。X和Y为最小覆盖中的点集
    int mincover(vector<int>& X,vector<int>& Y){
        int ans=solve();
        memset(S,0,sizeof(S));
        memset(T,0,sizeof(T));
        for(int u=0;u<n;u++)
            if(right[u]==-1)match(u);
        for(int u=0;u<n;u++)
            if(!S[u])X.push_back(u);
        for(int v=0;v<n;v++)
            if(T[v])Y.push_back(v);
        return ans;
    }
};
BPM solver;
int R,C,N;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int kase=0;
    while(cin>>R>>C>>N&&R&&C&&N){
        solver.init(R,C);
        for(int i=0;i<N;i++){
            int r,c;
            cin>>r>>c;r--;c--;
            solver.AddEdge(r,c);
        }
        vector<int>X,Y;
        int ans=solver.mincover(X,Y);
        cout<<ans;
        for(int i=0;i<X.size();i++)cout<<" r"<<X[i]+1;
        for(int j=0;j<Y.size();j++)cout<<" c"<<Y[j]+1;
        cout<<endl;
    }
    return 0;
}

Diposting di | Edited on

Golden Tiger Claw

UVA - 11383

题意

给一个n*n的矩阵，每个格子中有正整数w[i[j]，试为每行和每列分别确定一个数字row[i]和col[i]，使得任意格子w[i][j]<=row[i]+col[j]恒成立。先输row，再输出col，再输出全部总和（总和应尽量小）。

思路

本题与匹配无关，但可以用KM算法解决。

　　KM算法中的顶标就是保持了Lx[i]+ly[j]>=g[i[j]再求最大权和匹配的，但这个最大权和并没有关系。我们可以将row[i]看成一个男的，col[i]看成一个女的，这样男女的总数就相等。

　　一般来说，Lx[i]或Ly[i]仅需要取该行/列中最大的那个数即可保证满足要求，但是这样太大了，可以通过调整来使得总和更小。而KM算法的过程就是一个调整的过程，每一对匹配的男女的那条边的权值就会满足等号 wi[j]=row[i]+col[j]，至少需要一个来满足等号，这样才能保证row[i]+col[j]是达到最小的，即从j列看，col[j]满足条件且最小，从i行看，row[i]满足条件且最小。这刚好与KM算法求最大权和一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=5e2+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
int g[530][530];  ///存图
int nx,ny; /// 两边点数
bool visx[maxn],visy[maxn];
int slack[maxn];
int linker[maxn];   ///y中各点匹配状态
int lx[maxn],ly[maxn]; /// x,y中的点标号
bool dfs(int x){
    visx[x]=true;
    for(int y=0;y<ny;y++){
        if(visy[y])continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if(tmp==0){
            visy[y]=true;
            if(linker[y]==-1||dfs(linker[y])){
                linker[y]=x;return true;
            }
        }
        else if(slack[y]>tmp)slack[y]=tmp;
    }
    return false;
}
int KM(){
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(int i=0;i<nx;i++){
        lx[i]=-inf;
        for(int j=0;j<ny;j++){
            if(g[i][j]>lx[i])lx[i]=g[i][j];
        }
    }
    for(int x=0;x<nx;x++){
        for(int i=0;i<ny;i++)slack[i]=inf;
        while(true){
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x))break;
            int d=inf;
            for(int i=0;i<ny;i++)
                if(!visy[i]&&d>slack[i])d=slack[i];
            for(int i=0;i<nx;i++)
                if(visx[i])lx[i]-=d;
            for(int i=0;i<ny;i++)
                if(visy[i])ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int res=0;
    for(int i=0;i<ny;i++)
        if(linker[i]!=-1)res+=g[linker[i]][i];
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    while(cin>>n){
        nx=ny=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)cin>>g[i][j];
        int ans=KM();
        cout<<lx[0];
        for(int i=1;i<n;i++)cout<<" "<<lx[i];cout<<endl;
        cout<<ly[0];
        for(int i=1;i<n;i++)cout<<" "<<ly[i];cout<<endl;
        cout<<ans<<endl;
    }

    return 0;
}

Diposting di | Edited on

Airport Express

UVA - 11374

题意

机场快线有经济线和商业线,现在分别给出经济线和商业线的的路线,现在只能坐一站商业线,其他坐经济线,问从起点到终点的最短用时是多少,还有路线是怎样的;

题解

预处理出起点到所有站的最短距离和终点到所有站的最短距离,枚举要坐的那趟商业线,然后里面最小的就是答案了;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=550;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;              //点数和边数  点编号0~N-1
    vector<Edge>edges;
    vector<int>G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }

    void GetShortestPaths(int s,int* dist,vector<int>* paths){//paths是二维链表
        dijkstra(s);
        for(int i=0;i<n;i++){
            dist[i]=d[i];
            paths[i].clear();
            int t=i;
            paths[i].push_back(t);
            while(t!=s){
                paths[i].push_back(edges[p[t]].from);
                t=edges[p[t]].from;
            }
            reverse(paths[i].begin(),paths[i].end());
        }
    }
};

Dijkstra solver;
int d1[maxn],d2[maxn];
vector<int>paths1[maxn],paths2[maxn];
int main()
{
   // std::ios::sync_with_stdio(false);
   // std::cin.tie(0);
   // std::cout.tie(0);
    int kase=0,N,S,E,M,K,X,Y,Z;
    while(scanf("%d%d%d%d", &N, &S, &E, &M) == 4) {
        solver.init(N);
        S--;E--;
        for(int i=0;i<M;i++){
            scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
            solver.AddEdge(X,Y,Z);
            solver.AddEdge(Y,X,Z);
        }
        solver.GetShortestPaths(S,d1,paths1);
        solver.GetShortestPaths(E,d2,paths2);
        int ans=d1[E];
        vector<int>path=paths1[E];
        int midpoint=-1;
        scanf("%d", &K);
        for(int i=0;i<K;i++){
            scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
            for(int j=0;j<2;j++){
                if(d1[X]+d2[Y]+Z<ans){
                    ans=d1[X]+d2[Y]+Z;
                    path=paths1[X];
                    for(int p=paths2[Y].size()-1;p>=0;p--)
                        path.push_back(paths2[Y][p]);
                    midpoint=X;
                }
                swap(X,Y);
            }
        }
        
        if(kase != 0) printf("\n");
        kase++;
        for(int i = 0; i < path.size()-1; i++) printf("%d ", path[i]+1);
        printf("%d\n", E+1);
        if(midpoint == -1) printf("Ticket Not Used\n"); else printf("%d\n", midpoint+1);
        printf("%d\n", ans);
    }
    return 0;
}

Diposting di | Edited on

Bond

UVA - 11354

题意

给你一张无向图，然后有若干组询问，让你输出a->b的最小瓶颈路

题解

先求出最小生成树,然后对这个最小生成树做LCA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const int logmaxn=20;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct LCA{
    int n;
    int fa[maxn];       ///父亲数组
    int cost[maxn];     ///和父亲的费用
    int L[maxn];        ///层次(根节点为0)
    int anc[maxn][logmaxn];     /// anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i]
    int maxcost[maxn][logmaxn]; /// maxcost[p][i]是i和anc[p][i]的路径上的最大费用
    void preprocess(){
        for(int i=0;i<n;i++){
            anc[i][0]=fa[i];maxcost[i][0]=cost[i];
            for(int j=1;(1<<j)<n;j++)anc[i][j]=-1;
        }
        for(int j=1;(1<<j)<n;j++)
            for(int i=0;i<n;i++)
        if(anc[i][j-1]!=-1){
            int a=anc[i][j-1];
            anc[i][j]=anc[a][j-1];
            maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
        }
    }
    /// 求p到q的路径上的最大权
    int query(int p,int q){
        int tmp,log,i;
        if(L[p]<L[q])swap(p,q);
        for(log=1;(1<<log)<=L[p];log++);log--;
        int ans=-inf;
        for(int i=log;i>=0;i--)
        if(L[p]-(1<<i)>=L[q]){ans=max(ans,maxcost[p][i]);p=anc[p][i];}

        if(p==q)return ans; ///LCA为p

        for(int i=log;i>=0;i--)
        if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
            ans=max(ans,maxcost[p][i]);p=anc[p][i];
            ans=max(ans,maxcost[q][i]);q=anc[q][i];
        }
        ans=max(ans,cost[p]);
        ans=max(ans,cost[q]);
        return ans; ///LCA为fa[p]（它也等于fa[q]）
    }
};
LCA solver;
int pa[maxn];
int findset(int x){return pa[x]!=x?pa[x]=findset(pa[x]):x;}
vector<int>G[maxn],C[maxn];
void dfs(int u,int fa,int level){
    solver.L[u]=level;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v!=fa){
            solver.fa[v]=u;
            solver.cost[v]=C[u][i];
            dfs(v,u,level+1);
        }
    }
}

struct Edge{
    int x,y,d;
    bool operator <(const Edge& rhs)const{
        return d<rhs.d;
    }
};
const int maxm=1e5+10;
Edge e[maxm];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int kase=0,n,m,x,y,d,Q;
    while(cin>>n>>m){
        for(int i=0;i<m;i++){
            cin>>x>>y>>d;e[i]=(Edge){x-1,y-1,d};
        }
        sort(e,e+m);
        for(int i=0;i<n;i++){pa[i]=i;G[i].clear();C[i].clear();}
        for(int i=0;i<m;i++){
            int x=e[i].x,y=e[i].y,d=e[i].d,u=findset(x),v=findset(y);
            if(u!=v){
                pa[u]=v;
                G[x].push_back(y);G[y].push_back(x);
                C[x].push_back(d);C[y].push_back(d);
            }
        }
        solver.n=n;
        dfs(0,-1,0);
        solver.preprocess();
        if(++kase!=1)cout<<endl;
        cin>>Q;
        while(Q--){
            cin>>x>>y;
            cout<<solver.query(x-1,y-1)<<endl;
        }
    }
    return 0;
}

Diposting di | Edited on

The Largest Clique

UVA - 11324

题意

给一张有向图G，求一个结点数最大的结点集，使得该结点中任意两个结点 u 和 v满足：要么 u 可以到达 v， 要么 v 可以到达 u（u 和 v 相互可达也可以）。

题解

同一个强连通分量中的点要么都选，要么不选。把强连通分量收缩点后得到SCC图，让每个SCC结点的权等于它的结点数，则题目转化为求SCC图上权最大的路径。所以转化成了dp求DAG上的最长路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn],g[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt,sccnum[maxn];
stack<int>S;
void dfs(int u){
    pre[u]=lowlink[u]=++dfs_clock;
    S.push(u);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }
        else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            sccnum[scc_cnt]++;
            if(x==u)break;
        }
    }
}
void find_scc(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    memset(sccnum,0,sizeof(sccnum));
    for(int i=0;i<n;i++)
        if(!pre[i])dfs(i);
}
int d[maxn];
int dp(int i){
    int &ans=d[i];
    if(ans>=0)return ans;
    ans=sccnum[i];
    for(int j=0;j<g[i].size();j++){
        int v=g[i][j];
        ans=max(ans,dp(v)+sccnum[i]);
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
   // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<=n;i++)G[i].clear(),g[i].clear();
        int u,v;
        for(int i=0;i<m;i++){
            cin>>u>>v;
            u--;v--;
            G[u].push_back(v);
        }
        find_scc(n);
        memset(d,-1,sizeof(d));
        for(int u=0;u<n;u++)
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(sccno[u]!=sccno[v])
                g[sccno[u]].push_back(sccno[v]);
        }
        int ans=0;
        for(int i=1;i<=scc_cnt;i++)
            ans=max(ans,dp(i));
        cout<<ans<<endl;
    }

    return 0;
}

Diposting di | Edited on

Going in Cycle!!

UVA - 11090

题意

就最小的环的平均权值

题解

分枚举平均值mid，只需判断是否存在平均值小于mid的回路，即判断是否有sum(wi)<mid*k （1≤i≤k），只需判断是否有sum(wi-mid)<0，只需将边权值减去mid后，判断是否存在负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+10;
const int inf=1000000000;
struct Edge
{
    int from, to;
    double dist;
    Edge() {}
    Edge(int u, int v, double d) : from(u), to(v), dist(d) {}
};
struct BellmanFord{
    int n,m;
    vector<Edge>edges;
    vector<int> G[maxn];
    bool inq[maxn]; /// 是否在队列中
    double d[maxn];    /// s到各个点的距离  double 要改成double类型
    int p[maxn];    /// 最短路中的上一条弧
    int cnt[maxn];  /// 进队次数
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(from, to, dist);
        m = edges.size();
        G[from].push_back(m - 1);
    }
    bool bellmanford(int s){
        queue<int>Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } //如果只判负环用这个
        /*for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;inq[s]=true;Q.push(s);*/
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=false;
            for(auto& id:G[u]){
                Edge& e=edges[id];
                if(d[u]<inf && d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u] + e.dist;
                    p[e.to]=id;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)return true;
                    }
                }
            }
        }
        return false;
    }
};
BellmanFord solver;
bool test(double x){
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist-=x;
    bool ret=solver.bellmanford(0);
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist+=x;
    return ret;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++){
        int n,m;
        scanf("%d%d",&n,&m);
        solver.init(n);
        int ub=0;
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);u--;v--;ub=max(ub,w);
            solver.AddEdge(u,v,w);
        }
        printf("Case #%d: ", kase);
        if(!test(ub+1))printf("No cycle found.\n");
        else{
            double l=0,r=ub;
            while(r-l>1e-4){
                double mid=l+(r-l)/2;
                if(test(mid))r=mid;
                else l=mid;
            }
            printf("%.2f\n",l);
        }
    }
    return 0;
}

Diposting di | Edited on

Walk Through the Forest

UVA - 10917

题意

Jimmy打算每天沿着一条不同的路走，而且，他只能沿着满足如下条件的道路（A，B）：存在一条从B出发回家的路径，比所以从A出发回家的路径都短，你的任务是计算有多少条不同的路径

题意

题意就转化成如果终点到i 比到j的路劲短，就连线，然后记忆化搜索就行（这几天这种题做太多次了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1050;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;              ///点数和边数  点编号0~N-1
    vector<Edge>edges;    ///边列表
    vector<int>G[maxn];   ///每个节点出发的边编号
    bool done[maxn];      /// 是否已永久标号
    int d[maxn];          /// s到各个点的距离
    int p[maxn];          /// 最短路中的上一条边

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){ ///无向图调用两次
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
    /// dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）
    void GetShortestPaths(int s,int* dist,vector<int>* paths){///paths是二维链表
        dijkstra(s);
        for(int i=0;i<n;i++){
            dist[i]=d[i];
            paths[i].clear();
            int t=i;
            paths[i].push_back(t);
            while(t!=s){
                paths[i].push_back(edges[p[t]].from);
                t=edges[p[t]].from;
            }
            reverse(paths[i].begin(),paths[i].end());
        }
    }
};

Dijkstra solver;
int d[maxn];
int dp(int u){
    if(u==1)return 1;
    int &ans=d[u];
    if(ans>=0)return ans;
    ans=0;
    for(int i=0;i<solver.G[u].size();i++){
        int v=solver.edges[solver.G[u][i]].to;
        if(solver.d[v]<solver.d[u])ans+=dp(v);
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    while(cin>>n){
        if(n==0)break;
        cin>>m;
        solver.init(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;a--;b--;
            solver.AddEdge(a,b,c);
            solver.AddEdge(b,a,c);
        }
        solver.dijkstra(1);
        memset(d,-1,sizeof(d));
        cout<<dp(0)<<endl;
    }
    return 0;
}