一些图论题

Posted on Disqus:

一个给 B 层的模拟赛，感觉题选的不错（？

只改了题面、写了题解和删掉题目来源。

提高组图论测试5

后勤与同谋

R 国爆发了一场革命，有若干个有互相认识关系的人参与，他们之中有些人需要负责“后勤”，有些人需要负责“同谋”，但负责“后勤”的人必须两两互相认识，负责“同谋”的人必须两两不认识，每个人必须被划分到其中一个组织，请你求出划分的方案数。

输入格式

第一行一个整数n（2<=n<=5000）表示有n个人参与，标号为1…n。 之后有n行，第i行的第一个数ki（0<=ki<=n-1）表示i认识ki个人,随后的ki个数表示i的熟人。 p.s.输入满足：如果i是x的熟人，x会在i的序列中出现同时i也会出现在x的熟人序列中。

输出格式

符合条件的方案总数。

输入样例

1
2
3
4
5
4
2 2 3
2 1 3
3 1 2 4
1 3

输出样例

1
3

[解题思路]

首先对于每个点拆成两个点代表它去后勤和同谋，容易用 2-sat 求出一组解或判定无解。
发现任何一组解和这组解的差距不可能太大，具体来说，如果后勤组织少了两个人，那么这两个人就一定同时在同谋里了，这是不可能的，于是后勤和同谋都最多能少一个人，于是存在以下三种情况：

  • 一个同谋去了后勤
  • 一个后勤去了同谋
  • 一个同谋和一个后勤交换

前两种情况容易统计，判定是否有不合法的点在对方的就行。

第三种情况我们考虑统计每个点交换过去会产生多少组不合法的情况（比如一个同谋中的人在后勤中不认识的人的个数），发现这个数大于等于 2 的话一定无法交换，等于 1 的话交换过去判断是否合法，如果两个等于 0 的点交换的话，我们统计两边为 0 的点的个数为 x,yx,y ，这其中任意两个交换都合法，于是给答案加上 x×yx \times y 即可。

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
<!---Id=0 Type=Code S--->
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 5005
using namespace std;
char ch;
bool ok;
void read(int &x){
    for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    if (ok) x=-x;
}
int n,k,x,con[maxn],cnt0,cnt1,list0[maxn],list1[maxn],num[maxn],boom[maxn];
bool g[maxn][maxn],bo[maxn];
struct Graph{
    int tot,now[maxn<<1],son[maxn*maxn],pre[maxn*maxn];
    int idx,dfn[maxn<<1],low[maxn<<1],top,stack[maxn],cnt,bel[maxn<<1];
    bool in[maxn<<1];
    void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
    void dfs(int u){
        dfn[u]=low[u]=++idx,stack[++top]=u,in[u]=1;
        for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
            if (!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
            else if (in[v]) low[u]=min(low[u],dfn[v]);
        if (dfn[u]==low[u]){
            int v; ++cnt;
            do{v=stack[top--],in[v]=0,bel[v]=cnt;}while (v!=u);
        }
    }
}G;
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(k),con[i]=k;
        while (k--) read(x),g[i][x]=1;
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j){
        if (g[i][j]) G.put((i<<1)+1,j<<1); else G.put(i<<1,(j<<1)+1);
    }
    for (int i=2;i<=(n<<1)+1;i++) if (!G.dfn[i]) G.dfs(i);
    for (int i=1;i<=n;i++){
        if (G.bel[i<<1]==G.bel[(i<<1)+1]){puts("0");return 0;}
        if (G.bel[i<<1]<G.bel[(i<<1)+1]) list0[++cnt0]=i;
        else bo[i]=1,list1[++cnt1]=i;
    }
    int ans=(cnt0&&cnt1);
    for (int i=1;i<=cnt0;i++) for (int j=1;j<=cnt1;j++)
        if (g[list0[i]][list1[j]]) num[list0[i]]++,boom[list0[i]]=list1[j];
    for (int i=1;i<=cnt1;i++) for (int j=1;j<=cnt0;j++)
        if (!g[list1[i]][list0[j]]) num[list1[i]]++,boom[list1[i]]=list0[j];
    for (int i=1;i<=n;i++) if (num[i]==1){
        if (num[boom[i]]==1&&boom[i]>i&&boom[boom[i]]==i) ans++;
        else if (!num[boom[i]]) ans++;
    }
    int t0=0,t1=0;
    for (int i=1;i<=n;i++) if (!num[i]){
        if ((bo[i]&&cnt1>1)||(!bo[i]&&cnt0>1)) ans++;
        if (bo[i]) t1++; else t0++;
    }
    ans+=t1*t0;
    printf("%d\n",ans);
    return 0;
}

标志放置

一张无向图，对于边 (x,y)(x,y)，如果满足如下条件：

  • 从 xx 走到 yy 后如果不掉头（即将行进的方向调转 180°，你可以认为从一条路转到另一条不同的路时不会出现这种情况）则无法回到 x，

  • 如果能从 yy 不掉头走到一条边 (x′,y′)(x',y') 的 x′x' 端，并且 x′x' 这段有标记，则无需在 (x,y)(x,y) 的 xx 端放置标记，我们认为这是“多余的”。

则在 (x,y)(x,y) 这条边 xx 这一侧放一个「此路不通」标志，请你求出所有「此路不通」标志的位置。

输入格式

输入的第一行包含两个整数 n,m ，分别代表图中地点的数目和街道的数目。

接下来 m 行，每行包含两个整数 v,w ，表示这条街道连接了 u,v 两个地点。

输入保证不会给出重复的街道。

输出格式

第一行输出一个数字 k ，代表安装的「此路不通」标志的数量。

接下来 k 行，每行输出两个整数 v,w ，代表在连接 v,w 的街道的 v 入口处安装一个「此路不通」标志。

输出的街道应该先按 v 的升序进行排列，当 v 相同的时候，按照 w 的升序排列。

输入样例

1
2
3
4
5
6
6 5
1 2
1 3
2 3
4 5
5 6

输出样例

1
2
3
2
4 5
6 5

[解题思路]

首先这道题不是让你求割边。。。

比如下面这张图不需要放任何标志

1
2
3
4
5
6
7
1 2
2 3
1 3
1 4
4 5
5 6
6 4

通过一个环走回来再反向走这条边是合法的。

于是发现只有走进一棵树才会回不去，而对于一棵树，因为有题目中对多余的标志的限制，我们只需要在叶子处放标记（放在它到父亲的那条边自己这一侧）。

于是我们每次删除度数为 1 的节点，这样没法删的时候我们一定删了若干个树，此时存在的边一定不需要放任何标记，于是只对每一棵树分别处理即可，它们此时和单独的树没有区别。

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
<!---Id=0 Type=Code S--->
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;queue<int> q;pair<int,int> ans[500005];
int _ans=0,deg[500005],inq[500005];vector<int> g[500005];
int main() {
    int n,m,u,v;scanf("%d%d",&n,&m);
    for (register int i=0;i<m;++i) scanf("%d%d",&u,&v),
        g[u].push_back(v),g[v].push_back(u),++deg[u],++deg[v];
    for (register int i=1;i<=n;++i) sort(g[i].begin(),g[i].end());
    while (!q.empty()) q.pop();
    for (register int i=1;i<=n;++i) if (deg[i]==1) inq[i]=true,q.push(i);
    while (!q.empty()) {int cur=q.front();q.pop();
        for (register int ot:g[cur]) if (!inq[ot]&&--deg[ot]==1)
            inq[ot]=true,q.push(ot);
    }while (!q.empty()) q.pop();
    for (register int i=1;i<=n;++i) inq[i]=0;
    for (register int i=1;i<=n;++i) if (deg[i]>1)
        inq[i]=1,q.push(i);else inq[i]=0;
    while (!q.empty()) {int cur=q.front();q.pop();
        for (register int ot:g[cur]) if (!inq[ot])
            inq[ot]=1,q.push(ot);
    }for (register int i=1;i<=n;++i) for (register int ot:g[i]) {
        if (!inq[i]&&g[i].size()==1) ans[++_ans]=make_pair(i,ot);
        if (inq[i]&&deg[i]>1&&deg[ot]==1) ans[++_ans]=make_pair(i,ot);
    }printf("%d\n",_ans);
    for (register int i=1;i<=_ans;++i)
        printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}
<!---Id=0 Type=Code E--->

传感器排列

有一张 n*m 的地图，标有 ‘.’ 的为空地，标有 ‘*’ 的为玻璃，标有 ‘#’ 的为石头，我们需要在这片地上的空地中放置若干个传感器，每个传感器会向上、下、左、右四个方向发出四束光束，光束能穿透玻璃，不能穿透石头，我们不希望传感器能接受到来自其他传感器的光束干扰测量，同时我们希望放置尽可能多的传感器，请你求出这个数目最多为多少。

输入格式

第一行输入两个正整数n,m,n表示地图的行数，m表示地图的列数。1≤n,m≤50。接下来输入n行m列个字符，代表网格地图。*的个数不超过n*m个

输出格式

输出一个整数a，表示最多能放置传感器的个数

输入样例

1
2
3
4
5
4 4
#***
*#**
**#*
xxx#

输出样例

1
5

[解题思路]

如果没有石头那么每行、每列只能放一个传感器，于是的话可以每行建一个点，每列建一个点，把所有时空地的位置连一条边，跑最大匹配即可。

如果有石头的话那么放一个传感器只会导致一行中的一部分不可选，于是把每行、每列被石头分开的每一部分建一个点，依然依照上面的方法连边，发现并不会有什么区别。

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
<!---Id=0 Type=Code S--->
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;

#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define MREP(i,x) for(register int i=beg[x];i;i=E[i].last)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define inf INT_MAX
const int maxn=50+10;
int n,m,cnt,b[maxn*maxn],beg[maxn*maxn];
int num1[maxn][maxn],num2[maxn][maxn],cnt1,cnt2,ans;
char s[maxn][maxn];
bool vis[maxn*maxn];
struct edge{int to,last;}E[maxn*maxn];
void add(int u,int v){
    ++cnt;
    E[cnt].to=v;
    E[cnt].last=beg[u];
    beg[u]=cnt;
}
void init(){
    scanf("%d%d",&n,&m);
    REP(i,1,n)scanf("%s",s[i]+1);
    REP(i,1,n){
        ++cnt1;
        REP(j,1,n){
            if(s[i][j]=='x')
                continue;
            if(s[i][j]=='#')
                ++cnt1;
            else if(s[i][j]=='*')
                num1[i][j]=cnt1;
        }
    }
    REP(j,1,m){
        ++cnt2;
        REP(i,1,n){
            if(s[i][j]=='x')
                continue;
            if(s[i][j]=='#')
                ++cnt2;
            else if(s[i][j]=='*')
                num2[i][j]=cnt2;
        }
    }
    REP(i,1,n){
        REP(j,1,m){
            if(s[i][j]=='x' || s[i][j]=='#')
                continue;
            add(num1[i][j],num2[i][j]);
        }
    }
}
bool dfs(int u){
    MREP(i,u){
        int v=E[i].to;
        if(vis[v])continue;
        vis[v]=1;
        if(!b[v] || dfs(b[v])){
            b[v]=u;
            return true;
        }
    }
    return false;
}
int main(){
    init();
    REP(i,1,cnt1){
        ans+=dfs(i);
        mem(vis);
    }
    printf("%d\n",ans);
    return 0;
}
<!---Id=0 Type=Code E--->

传送

有一张 n 个点，m 条边的有向图，你走过一条边不需要代价，但你经过这条边的次数有一定的限制，同时你可以花费 1 的代价从任何节点传送到任何节点，请你求出满足访问第 i 个点恰好 FiF_i 次的方案的最小代价。

我们用u、v、w三个参数描述一条边，表示从节点u到节点v有一条最多可以经过w次的边（不一定要经过w次）。值得注意的是，对于任意一对边(u1,v1)和(u2,v2)，如果有 u1<u2，则有v1≤v2；如果有 v1<v2，则有u1≤u2且 u1=u2和v1=v2不同时成立。 你可以从任意的节点开始，从任意的节点结束。出发去开始的节点需要花费 1 的代价。

输入格式

第一行包含两个正整数n、m，意义见题目描述。第二行包含n个正整数，第i个数表示Fi。接下来有m行，每行有三个正整数u、v、w，表示从节点u到节点v有一条最多可以经过w次的边。

输出格式

输出一行一个整数，表示方案的最小代价。

输入样例

1
2
3
4
5
4 3
5 5 5 5
1 2 1
3 2 1
3 4 1

输出样例

1
17

[解题思路]

首先发现那个奇怪的条件一定强于图上没有环，因为最后一条回去的边一定不合法，至于它具体在说什么我也不清楚。。。

最小路径覆盖：

给定一张 DAG，要求你选出若干条长度大于等于 0 的路径，使得每个点恰好在一条路径上。

首先一个通解是每个点作为一条路径，之后如果两条路径间直接有路径相连，我们可以将它们连接并把答案减一。

考虑找到最优解，我们把每个点拆成两个，出点和入点，原图上的每一条边转化成对应的出点向入点连边，我们求出这张图的最大匹配，一条边被选中就相当于将它两边的两条路径合并，这两条路径一定存在（只是可能长度为 0，而且因为原图无环怎么选都是合法的），于是总点数-最大匹配就是答案。

而这道题就相当于把每条边拆成 w 条，答案就是 ∑Fi\sum F_i - 最大匹配，原理和上面一样。

BZOJ2163

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
<!---Id=0 Type=Code S--->
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

const int max_n=1e4+5;
const int max_m=1e5+5;
const int max_N=max_n*2+2;
const int max_M=max_n*2+max_m;
const int max_e=max_M*2;
const int inf=1e9;

int n,m,N,sum,x,y,cap,maxflow;
int F[max_n];
int point[max_N],nxt[max_e],v[max_e],remain[max_e],tot;
int deep[max_N],cur[max_N];
queue <int> q;

inline void add(int x,int y,int cap){
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;
}

inline bool bfs(int s,int t){
    memset(deep,0x7f,sizeof(deep));
    deep[s]=0;
    for (int i=1;i<=N;++i)
      cur[i]=point[i];
    while (!q.empty()) q.pop();
    q.push(s);

    while (!q.empty()){
        int now=q.front(); q.pop();
        for (int i=point[now];i!=-1;i=nxt[i])
          if (deep[v[i]]>inf&&remain[i]){
            deep[v[i]]=deep[now]+1;
            q.push(v[i]);
          }
    }

    return deep[t]<inf;
}

inline int dfs(int now,int t,int limit){
    if (!limit||now==t) return limit;
    int flow=0,f;

    for (int i=cur[now];i!=-1;i=nxt[i]){
        cur[now]=i;
        if (deep[v[i]]==deep[now]+1&&(f=dfs(v[i],t,min(limit,remain[i])))){
            flow+=f;
            limit-=f;
            remain[i]-=f;
            remain[i^1]+=f;
            if (!limit) break;
        }
    }
    return flow;
}

inline void dinic(int s,int t){
    while (bfs(s,t))
      maxflow+=dfs(s,t,inf);
}

int main(){
    tot=-1;
    memset(point,-1,sizeof(point));
    memset(nxt,-1,sizeof(nxt));

    scanf("%d%d",&n,&m);
    N=2+2*n;

    for (int i=1;i<=n;++i){
        scanf("%d",&F[i]);
        add(1,i+1,F[i]);
        add(i+1+n,N,F[i]);
        sum+=F[i];
    }
    for (int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&cap);
        add(x+1,1+n+y,cap);
    }

    dinic(1,N);

    printf("%d\n",sum-maxflow);
}