Diposting di | Edited on

Qin Shi Huang’s National Road System

UVALive - 5713

题意

有n个城市，要修一些路使得任意两个城市都能连通。但是有人答应可以不计成本的帮你修一条路，为了使成本最低，你要慎重选择修哪一条路。假设其余的道路长度为B，那条别人帮忙修的道路两端城市中的总人口为B，要找一个使A/B最大的方案。

题意

先求最小生成树，处理出MST中任意两点之间的最长边。因为别人只答应给修一条路，所以枚举这条路，用这条路替换下一条MST中最长的边（在加入这条路后构成的环中），比较求得A/B的最大值。实际上是把求次小生成树的一些后续操作改改。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,x[maxn],y[maxn],p[maxn];

int pa[maxn];
int findset(int x){return pa[x]!=x?pa[x]=findset(pa[x]):x;}
vector<int>G[maxn];
vector<double>C[maxn];

struct Edge{
    int x,y;
    double d;
    bool operator < (const Edge& rhs)const{
        return d<rhs.d;
    }
};

Edge e[maxn*maxn];
double maxcost[maxn][maxn];
vector<int>nodes;

void dfs(int u,int fa,double facost){
    //cout<<"dfs="<<u<<endl;
    for(int i=0;i<nodes.size();i++){
        int x=nodes[i];
        maxcost[u][x]=maxcost[x][u]=max(maxcost[x][fa],facost);
    }
    nodes.push_back(u);
    for(int i=0;i<G[u].size();i++){
        if(G[u][i]==fa)continue;
        dfs(G[u][i],u,C[u][i]);
    }
}
double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double MST(){
    m=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
    e[m++]=(Edge){i,j,dis(i,j)};
    sort(e,e+m);
    for(int i=0;i<n;i++){pa[i]=i;G[i].clear();C[i].clear();}
    int cnt=0;
    double ans=0;
    for(int i=0;i<m;i++){
        int x=e[i].x,y=e[i].y,u=findset(x),v=findset(y);
        double d=e[i].d;
        if(u==v)continue;
        pa[u]=v;
        G[x].push_back(y);G[y].push_back(x);
        C[x].push_back(d);C[y].push_back(d);
        ans+=d;
        if(++cnt==n-1)break;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>p[i];
        double tot=MST();
        memset(maxcost,0,sizeof(maxcost));
        nodes.clear();
        dfs(0,-1,0);
        double ans=-1;
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            ans=max(ans,(p[i]+p[j])/(tot-maxcost[i][j]));
        }
        cout<<fixed<<setprecision(2)<<ans<<endl;
    }
    return 0;
}

Diposting di | Edited on

Mining Your Own Business

UVALive - 5135

题意

在一张无向图中，将一些点涂上黑色，使得删掉图中任何一个点时，每个连通分量至少有一个黑点。问最少能涂几个黑点，并且在涂最少的情况下有几种方案。

显然，一定不能涂割点。对于每一个连通分量，如果有1个割点，则必须涂上分量内除割点之外的任意一个点，如果有多个（2个及以上）割点，则这个分量不需要涂色。如果整张图都没有割点，那么任选两个点涂色即可，之所以要涂两个，是要防止删掉的电恰是黑点的情况。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

struct Edge{
    int u,v;
};
///割顶 bccno 无意义
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;
vector<int>G[maxn],bcc[maxn];
stack<Edge>S;
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v =G[u][i];
        Edge e = (Edge){u,v};
        if(!pre[v]){ ///没有访问过
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu=min(lowu, lowv);                ///用后代更新
            if(lowv >= pre[u]){
                iscut[u]=true;
                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始
                for(;;){
                    Edge x=S.top();S.pop();
                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}
                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}
                    if(x.u==u&&x.v==v)break;
                }
            }
        }
        else if(pre[v] < pre[u] && v !=fa){
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cut = 0;
    for(int i = 0; i < n;i++)
        if(!pre[i])dfs(i,-1);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,Case=1;
    int mx;
    while(cin>>n&&n){
        for(int i=0;i<2*n;i++)G[i].clear();
        mx=-inf;
        for(int i=0;i<n;i++){
            int u,v;
            cin>>u>>v;mx=max(mx,max(u,v));
            u--,v--;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        find_bcc(mx);
        ll ans1=0,ans2=1;
        for(int i=1;i<=bcc_cut;i++){
            int cut_cnt=0;
            for(int j=0;j<bcc[i].size();j++)
                if(iscut[bcc[i][j]])cut_cnt++;
            if(cut_cnt==1){
                ans1++;
                ans2*=(ll)(bcc[i].size()-cut_cnt);
            }
        }
        if(bcc_cut==1){
            ans1=2;
            ans2=ll(bcc[1].size()*(bcc[1].size()*1LL-1LL)/2LL);
        }
        cout<<"Case "<<Case++<<": "<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

Diposting di | Edited on

Proving Equivalences

UVALive - 4287

题意

有n个命题，已知其中的m个推导，要证明n个命题全部等价（等价具有传递性），最少还需要做出几次推导。

题解

由已知的推导可以建一张无向图，则问题变成了最少需要增加几条边能使图变成强连通图。找出所有的强连通分量，将每一个连通分量视作一个大节点，则整张图变成了一张DAG。设出度为0的大节点个数为a，入度为0的大节点个数为b，则答案就是max(a,b)。为什么是这样呢？因为要使等价证明前进下去，每个大节点的出度和入度都必须不能是0。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
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;
            if(x==u)break;
        }
    }
}
void find_scc(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;i++)
        if(!pre[i])dfs(i);
}
int in[maxn],out[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<=n;i++)G[i].clear();
        for(int i=0;i<m;i++){
            int u,v;
            cin>>u>>v;u--;v--;
            G[u].push_back(v);
        }
        find_scc(n);
        for(int i=1;i<=scc_cnt;i++)in[i]=out[i]=1;
        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])in[sccno[v]]=out[sccno[u]]=0;
        }
        int a=0,b=0;
        for(int i=1;i<=scc_cnt;i++){
            if(in[i])a++;
            if(out[i])b++;
        }
        if(scc_cnt==1)cout<<0<<endl;
        else cout<<max(a,b)<<endl;
    }
    return 0;
}

Diposting di | Edited on

Warfare And Logistics

UVALive - 4080

题意

①先求任意两点间的最短路径累加和，其中不连通的边权为L ②删除任意一条边,求全局最短路径和的最大值

题解

刚看到题目是让各点之间的最短路径和，所以立马想到啦floyd算法求最短路，然后发现还要去掉一条边后求最短路中的最大值，则floyd会超时，所以打算用dijkstra+堆优化做，首先枚举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
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+10;
const int inf=1000000000;
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(e.dist>0&&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});
                }
            }
        }
    }
};

Dijkstra solver;
int n,m,L;
vector<int>gr[maxn][maxn];
int used[maxn][maxn][maxn];
int idx[maxn][maxn];
int sum_single[maxn];

int compute_c(){
    int ans=0;
    memset(used,0,sizeof(used));
    for(int src=0;src<n;src++){
        solver.dijkstra(src);
        sum_single[src]=0;
        for(int i=0;i<n;i++){
            if(i!=src){
                int fa=solver.edges[solver.p[i]].from;
                used[src][fa][i]=used[src][i][fa]=1;
            }
            sum_single[src]+=(solver.d[i]==inf?L:solver.d[i]);
        }
        ans+=sum_single[src];
    }
    return ans;
}
int compute_newc(int a,int b){
    int ans=0;
    for(int src=0;src<n;src++)
        if(!used[src][a][b])ans+=sum_single[src];
        else{
            solver.dijkstra(src);
            for(int i=0;i<n;i++)
                ans+=(solver.d[i]==inf?L:solver.d[i]);
        }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>n>>m>>L){
        solver.init(n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)gr[i][j].clear();
        for(int i=0;i<m;i++){
            int a,b,s;
            cin>>a>>b>>s;a--;b--;
            gr[a][b].push_back(s);
            gr[b][a].push_back(s);
        }
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)if(!gr[i][j].empty()){
            sort(gr[i][j].begin(),gr[i][j].end());
            solver.AddEdge(i,j,gr[i][j][0]);
            idx[i][j]=solver.m-1;
            solver.AddEdge(j,i,gr[i][j][0]);
            idx[j][i]=solver.m-1;
        }
        int c=compute_c();
        int c2=-1;
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)if(!gr[i][j].empty()){
            int &e1=solver.edges[idx[i][j]].dist;
            int &e2=solver.edges[idx[j][i]].dist;
            if(gr[i][j].size()==1)e1=e2=-1;
            else e1=e2=gr[i][j][1];
            c2=max(c2,compute_newc(i,j));
            e1=e2=gr[i][j][0];
        }
        cout<<c<<" "<<c2<<endl;
    }
    return 0;
}

Diposting di | Edited on

Ants

UVALive - 4043

题意

给你n个白点和n个黑点的平面坐标，要求用n条不相交的线连起来，每条线段连一个白点和黑点，每个点连一条线，也就是匹配。让你输出第i个白点所对应的黑点。

思路

二分图完美匹配问题。但是题目中有个线段不相交，怎么办？其实这个最佳完美匹配就是答案了。最佳完美匹配是权值和最大，那么我们就把两两点线段的权值搞成他们距离的负数即可。这样就不可能有相交的了。为什么？因为假设有相交，a1-b2，a2-b1，而dist(a1,b1)+dist(a2,b2) 肯定比前面交叉的小，画个四边形就很清楚了，那么负数就是大了，也就是说交叉的在我们设计的负权那里是小的，所以就是最佳，也就是不可能有交叉的。

这样分析清楚了之后，就只要直接套用KM就OK了！

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e2+50;
const double inf=999999999999999.;
const double eps=1e-5;
struct node{
    double x,y;
}white[150],black[150];
double g[150][150];
int nx,ny;
bool visx[maxn],visy[maxn];
double slack[maxn];
int linker[maxn];
double lx[maxn],ly[maxn];
bool dfs(int x){
    visx[x]=true;
    for(int y=0;y<ny;y++){
        if(visy[y])continue;
        double tmp=lx[x]+ly[y]-g[x][y];
        if(fabs(tmp)<eps){
            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;
            double 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;
}

double dis(node a,node b){
    return double(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
int n;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int first=0;
    while(cin>>n){
        nx=ny=n;
        if(first)cout<<endl;
        first=1;
        for(int i=0;i<n;i++){
            cin>>white[i].x>>white[i].y;
        }
        for(int i=0;i<n;i++){
            cin>>black[i].x>>black[i].y;
        }
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=-dis(black[i],white[j]);
        KM();
        for(int i=0;i<n;i++)cout<<linker[i]+1<<endl;
    }
    return 0;
}

Diposting di | Edited on

Ladies’ Choice

UVALive - 3989

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
#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;
int pref[maxn][maxn],order[maxn][maxn],Next[maxn],future_husband[maxn],future_wife[maxn];
queue<int>Q;
void engage(int man,int woman){
    int m=future_husband[woman];
    if(m)future_wife[m]=0,Q.push(m);
    future_wife[man]=woman;
    future_husband[woman]=man;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
                cin>>pref[i][j];
            Next[i]=1;
            future_wife[i]=0;
            Q.push(i);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int x;cin>>x;
                order[i][x]=j;
            }
            future_husband[i]=0;
        }
        while(!Q.empty()){
            int man=Q.front();Q.pop();
            int woman=pref[man][Next[man]++];
            if(!future_husband[woman])engage(man,woman);
            else if(order[woman][man]<order[woman][future_husband[woman]])engage(man,woman);
            else Q.push(man);
        }
        while(!Q.empty())Q.pop();
        for(int i=1;i<=n;i++)cout<<future_wife[i]<<endl;
        if(t)cout<<endl;
    }
    return 0;
}

Diposting di | Edited on

Astronauts

UVALive - 3713

题意

有A,B,C三个人物要分配个N个宇航员，每个宇航员恰好要分配一个任务，设平均年龄为X，只有年龄大于或等于X的宇航员才能分配任务A。只有年龄严格小于X的宇航员才能分配任务B。而任务C没有限制。有M对宇航员相互讨厌，因此不能分配到同一任务。编程找出一个满足上述所有要求的任务分配方案。

题解

如果憎恶就代表不能一起去C，如果年龄相同就代表不能一起去A/B；

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=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct TwoSAT{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x){
        if(mark[x^1])return false;
        if(mark[x])return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i]))return false;
        return true;
    }

    void init(int n){
        this->n=n;
        for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
    }
    /// x=xval or y= yval;
    void add_caluse(int x,int xval,int y,int yval){
        x=x*2+xval;
        y=y*2+yval;
        G[x^1].push_back(y);///如果x为真 那么y必须为假;
        G[y^1].push_back(x);///如果y为真 那么x必须为假;
    }

    bool solve(){
        for(int i=0;i<n*2;i+=2)
        if(!mark[i]&&!mark[i+1]){
            c=0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]]=false;
                if(!dfs(i+1))return false;
            }
        }
        return true;
    }
};
int n,a[maxn],m;
TwoSAT solver;
int tol;
int is_young(int x){
    return a[x]*n<tol;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>n>>m&&n&&m){
        tol=0;
        solver.init(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
            tol+=a[i];
        }
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;a--;b--;
            solver.add_caluse(a,1,b,1);
            if(is_young(a)==is_young(b))
                solver.add_caluse(a,0,b,0);
        }
        if(!solver.solve())cout<<"No solution."<<endl;
        else for(int i=0;i<n;i++)
            if(solver.mark[i*2])cout<<"C"<<endl;
        else if(is_young(i))cout<<"B"<<endl;
        else cout<<"A"<<endl;
    }
    return 0;
}

Diposting di | Edited on

Knights of the Round Table

UVALive - 3523

题意

圆桌骑士。有的骑士之间是相互憎恨的，不能连坐，需要安排奇数个骑士围着桌子坐着，大于3个，求哪些骑士不可能安排到座位。

根据给定的关系，如果两个骑士之间没有憎恨关系，那么连边。最终就是求有多少个点无法位于奇圈之内。根据二分图可以知道二分图的都是偶数圈；所以只要先把联通分量求出来然后判断是否是二分图就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

bool A[maxn][maxn];
struct Edge{
    int u,v;
};
///割顶 bccno 无意义
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;
vector<int>G[maxn],bcc[maxn];
stack<Edge>S;
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v =G[u][i];
        Edge e = (Edge){u,v};
        if(!pre[v]){ ///没有访问过
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu=min(lowu, lowv);                ///用后代更新
            if(lowv >= pre[u]){
                iscut[u]=true;
                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始
                for(;;){
                    Edge x=S.top();S.pop();
                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}
                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}
                    if(x.u==u&&x.v==v)break;
                }
            }
        }
        else if(pre[v] < pre[u] && v !=fa){
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cut = 0;
    for(int i = 0; i < n;i++)
        if(!pre[i])dfs(i,-1);
}

int odd[maxn], color[maxn];
bool bipartite(int u,int b){
    for(int i = 0;i < G[u].size(); i++){
        int v =G[u][i]; if(bccno[v] != b) continue;
        if(color[v] == color[u])return false;
        if(!color[v]){
            color[v] = 3 - color[u];
            if(!bipartite(v,b))return false;
        }
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int kase=0,n,m;
    while(cin>>n>>m&&n){
        for(int i=0;i<n;i++) G[i].clear();

        memset(A,0,sizeof(A));
        for(int i=0;i<m;i++){
            int u,v;
            cin>>u>>v;
            u--;v--;
            A[u][v]=A[v][u]=1;
        }
        for(int u=0;u<n;u++){
            for(int v=u+1;v<n;v++){
                if(!A[u][v]){
                    G[u].push_back(v);
                    G[v].push_back(u);
                }
            }
        }

        find_bcc(n);

        memset(odd, 0, sizeof(odd));
        for(int i = 1; i <= bcc_cut; i++){
            memset(color, 0, sizeof(color));
            for(int j = 0;j < bcc[i].size(); j++) bccno[bcc[i][j]]=i;

            int u=bcc[i][0];
            color[u]=1;
            if(!bipartite(u,i))
                for(int j = 0;j < bcc[i].size(); j++)odd[bcc[i][j]]=1;
        }
        int ans=n;
        for(int i = 0; i < n; i++)if(odd[i])ans--;
        cout<<ans<<endl;

    }
    return 0;
}

Diposting di | Edited on

Guardian of Decency

UVALive - 3415

我们将男女分开来 就可以建出一个二分图，对于任意的男女生 只要上边四个条件一个也不满足 就表示不能同时去 ，那么我们在其中间连一条边，那么最终的结果就是我们从中取出尽量多的点，使得任意两个点之间没有连线。那么问题就转化成了求最大点独立集。 二分图的最大点独立集= 总点数 - 最大匹配（最小点覆盖）

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=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;
struct node{
    int h;
    string m,s;
    node(int h,string m,string s):h(h),m(m),s(s){}
};
bool ok(node a,node b){
    return abs(a.h-b.h)<=40&&a.m==b.m&&a.s!=b.s;
}
int R,C,N;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<node>a,b;
        for(int i=0;i<n;i++){
            int h;string m,s,sex;
            cin>>h>>sex>>m>>s;
            if(sex[0]=='M')a.push_back(node(h,m,s));
            else b.push_back(node(h,m,s));
        }
        int x=a.size(),y=b.size();
        solver.init(x,y);
        for(int i=0;i<x;i++)
            for(int j=0;j<y;j++)
            if(ok(a[i],b[j]))solver.G[i][j]=1;
        cout<<x+y-solver.solve()<<endl;
    }
    return 0;
}

Diposting di | Edited on

Now or later

UVALive - 3211

题意

n架飞机，每架可选择两个着落时间。安排一个着陆时间表，使得着陆间隔的最小值最大

题解

二分查找最大值P，每次都用2—SAT判断是否可行。

假设A早和B早的时间会冲突，那么我们就要规定，A晚或者B晚，规定其中一个必须要晚，

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct TwoSAT{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x){
        if(mark[x^1])return false;
        if(mark[x])return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i]))return false;
        return true;
    }

    void init(int n){
        this->n=n;
        for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
    }
    /// x=xval or y= yval;
    void add_caluse(int x,int xval,int y,int yval){
        x=x*2+xval;
        y=y*2+yval;
        G[x^1].push_back(y);///如果x为真 那么y必须为假;
        G[y^1].push_back(x);///如果y为真 那么x必须为假;
    }

    bool solve(){
        for(int i=0;i<n*2;i+=2)
        if(!mark[i]&&!mark[i+1]){
            c=0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]]=false;
                if(!dfs(i+1))return false;
            }
        }
        return true;
    }
};
int n,T[maxn][2];
TwoSAT solver;

bool test(int diff){
    solver.init(n);
    for(int i=0;i<n;i++)for(int a=0;a<2;a++)
        for(int j=i+1;j<n;j++)for(int b=0;b<2;b++)
        if(abs(T[i][a]-T[j][b])<diff)solver.add_caluse(i,a^1,j,b^1);
    return solver.solve();
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>n&&n){
        int L=0,R=0;
        for(int i=0;i<n;i++)for(int a=0;a<2;a++){
            cin>>T[i][a];
            R=max(T[i][a],R);
        }
        int ans=0;
        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;
}