Starry

发表于 更新于 分类于 本文字数： 565 阅读时长 ≈ 2 分钟

首先考虑建图，因为

每个男孩最多只愿意和个不喜欢的女孩跳舞，而每个女孩也最多只愿意和个不喜欢的男孩跳舞。

所以对于每个男孩女孩均要建一个辅助点，到该点的权值为，对于互相喜欢的男女孩相连，权值为，对于不喜欢的，则他们的辅助点相连，权值亦为。

接下来考虑源点到男孩与女孩到汇点的权值情况。

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
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
const int N = 2e4 + 86;

struct egdes
{
    int to, nxt, w;
} e[N * 2];
int hd[N * 2], cur[N * 2], tot = 1, st, en;
vi lv;
void add(int x, int y, int w)
{
    e[++tot] = (egdes){y, hd[x], w};
    hd[x] = tot;
}

int bfs()
{
    lv.assign(N, 0);
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st] = 1;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol && !lv[to])
            {
                lv[to] = lv[p] + 1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss, int flow)
{
    if (ss == en)
        return flow;
    int r = flow;
    for (int eg = cur[ss]; eg && r; eg = e[eg].nxt)
    {
        cur[ss] = eg;
        int to = e[eg].to, vol = e[eg].w;
        if (vol && lv[to] == lv[ss] + 1)
        {
            int c = dfs(to, min(r, vol));
            r -= c;
            {
                e[eg].w -= c;
                e[eg ^ 1].w += c;
            }
        }
    }
    return flow - r;
}
int n, k;
vi rim[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    st = 6 * n + 86, en = st + 1;
    f(j, 1, n)
    {
        string s;
        cin >> s;
        //if(s.length()!=n)cout<<s.length();
        f(i, 1, n)
        {
            if (s[i - 1] == 'Y')
                rim[j].pb(i);
            else
                rim[j + n].pb(i);
        }
    }
    int l=0,r=n;
    while (l<r)
    {
        memset(hd, 0, sizeof(hd));
        tot = 1;
        int mid=(l+r+1)>>1;
        f(i, 1, n)
        {
            add(st, i, mid);
            add(i, st, 0);
            add(i, i + 2 * n, k);
            add(i + 2 * n, i, 0);
            add(i+4*n,i+n,k);
            add(i+n,i+4*n,0);
            add(i + n, en, mid);
            add(en, i + n, 0);
            for (auto it : rim[i])
            {
                add(i, it + n, 1);
                add(it + n, i, 0);
            }
            for (auto it : rim[i + n])
            {
                add(i + 2 * n, it +4* n, 1);
                add(it + 4*n, i + 2 * n, 0);
            }
        }
        LL ans = 0;
        while (bfs())
        {
            ans += dfs(st, 3e8);
        }
        if (mid * n == ans)
        {
            l=mid;
        }
        else r=mid-1;
    }
    cout <<l;
    return 0;
}

发表于 更新于 分类于 本文字数： 386 阅读时长 ≈ 1 分钟

最小割，注意边e要估好，不然RE走起

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
const LL N = 5e3 + 86;
LL n, m; //n+1,n+2起始和终点，n+3以后虚点
struct edges
{
    int to, nxt,w;
} e[N*200];
int tot = 1, hd[N*100], cur[N*100];
void add(int x, int y, int v)
{
    e[++tot]=(edges){y,hd[x],v};hd[x]=tot;
}

int lv[N];
int bfs(int ss,int end)
{
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(ss);
    lv[ss] = 1;
    while (!q.empty())
    {
        int p = q.front();
        //cout<<p<<":::"<<e[hd[p]].to<<":::"<<e[hd[p]].w<<"\n";
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            //cout<<"##"<<to<<"::"<<vol<<"\n";
            if (vol>0&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    //cout<<lv[end]<<"\n";
    return lv[end];
}

LL dfs(int p,int flow){
    if(p==n+2)
    return flow;
   LL r=flow;
    for(int eg=cur[p];eg&&r;eg=e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol>0&&lv[to]==lv[p]+1){
            
            int c=dfs(to,min(vol*1ll,r));
            //cout<<p<<"::"<<to<<vol<<c<<"\n";
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //IN;OUT;
    cin >> n;
    LL s = 0;
    int x;
    f(i, 1, n)
    {
        cin >> x;
        s+=x;
        add(n + 1, i, x);
        add(i, n + 1, 0);
    }
    f(i,1,n){
        cin>>x;
        s+=x;
        add(i,n+2,x);
        add(n+2,i,0);
    }
    cin>>m;
    //cout<<"ook";
    f(i, 1, m)
    {
        int cn = n + 2 + 2 * i, k, te1, te2, ddd;
        cin >> k >> te1 >> te2;
        s+=(te1+te2);
        add(n + 1, cn - 1, te1);
        add(cn - 1, n + 1, 0);
        add(cn, n + 2, te2);
        add(n + 2, cn, 0);
        //cout<<i<<endl;
        f(i, 1, k)
        {
            cin >> ddd;
            add(cn - 1, ddd, 3e8);
            add(ddd, cn - 1, 0);
            add(ddd, cn, 3e8);
            add(cn, ddd, 0);
        }
    }
    LL ans=0;
    //cout<<"Ok"<<"\n";
    //return 0;
    while(bfs(n+1,n+2)){
        //cout<<ans;
        ans+=dfs(n+1,3e8);
    }
    cout<<s-ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 274 阅读时长 ≈ 1 分钟

P1345 [USACO5.4]奶牛的电信Telecowmunication

转化为最小割，注意起始点为i+n

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
const int N=12000+96;
struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
	e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,s,su,lv[N];

int bfs(){
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd)); // 当前弧优化初始化
    queue<int> q;
    q.push(s);
    lv[s]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1,q.push(to);
            }
        }
    }
    return  lv[n];
}

int dfs(int p,int flow){
    if(p==n)
    return flow;
    int r=flow;
    for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol&&lv[to]==lv[p]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>su>>m>>s>>n;
    s+=su;
    f(i,1,su)
    {
    add( i, i+su, 1 ) ; add( i+su, i, 0 ) ;
    }
    f(i,1,m){
        int aa,bb;
        cin>>aa>>bb;
        add(aa+su,bb,1);
        add(bb,aa+su,0);  
        add(bb+su,aa,1);
        add(aa,bb+su,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(s,3e8);
    }
   cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 384 阅读时长 ≈ 1 分钟

洛谷P1343最大流问题的Dinic解法，bfs分层然后dfs增广，还得捋捋弧优化

因为在Dinic算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把head数组复制一份，但不断更新增广的起点。

UPD:原来是这里写错了 
1
for(int eg=hd[p];eg;eg=e[eg].nxt)
 应该是 
1
for (int eg = cur[p]; eg && r; eg = e[eg].nxt)
于是对于每次dfs完之后，cur数组指向该点上次dfs的边下标 
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
const int N=2e3+86;
struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
	e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,x,lv[N];

int bfs(){
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd)); // 当前弧优化初始化
    queue<int> q;
    q.push(1);
    lv[1]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1,q.push(to);
            }
        }
    }
    return  lv[n];
}

int dfs(int p,int flow){
    if(p==n)
    return flow;
    int r=flow;
    for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol&&lv[to]==lv[p]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    f(i,1,m){
        int aa,bb,cc;
        cin>>aa>>bb>>cc;
        add(aa,bb,cc);
        add(bb,aa,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(1,3e8);
    }
    if(ans)cout<<ans<<" "<<(x-1)/ans+1;
    else cout<<"Orz Ni Jinan Saint Cow!";
    return 0;
}

发表于 更新于 分类于 本文字数： 254 阅读时长 ≈ 1 分钟

用EK算法来做最大流问题，相较于FF算法，EK算法先用bfs找出最小流，然后从汇点开始扣减容量到汇点

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

const int N = 2e3 + 86;
struct edge
{
    int to, nxt, w;
} e[N * 2];
int hd[N], tot = 1;
void add(int u, int v, int w)
{
    e[++tot] = (edge){v, hd[u], w};
    hd[u] = tot;
}
int n, m, x, flow[N], last[N];
bitset<286> vis;

int bfs()
{
    memset(last, 0, sizeof(last));
    queue<int> q;
    q.push(1);
    flow[1] = 9e8 + 86;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        if (p == n)
            break;
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol > 0 && !last[to])
            {
                last[to] = eg;
                flow[to] = min(flow[p], vol);
                q.push(to);
            }
        }
    }
    return last[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //IN;OUT;
    cin >> n >> m >> x;
    f(i, 1, m)
    {
        int x, y, val;
        cin >> x >> y >> val;
        add(x, y, val);
        add(y, x, 0);
    }
    LL ans = 0;
    while (bfs())
    {
        ans += flow[n];
        for (int i = n; i != 1; i = e[last[i] ^ 1].to) // 从汇点原路返回更新残余容量
        {
            e[last[i]].w -= flow[n];
            e[last[i] ^ 1].w += flow[n];
        }
    }
    if (ans)
    {
        cout << ans << " ";
        cout << (x / ans + (x % ans ? 1 : 0));
    }
    else
        cout << "Orz Ni Jinan Saint Cow!";
    return 0;
}
0%