6
23
2015
0

bzoj 4155: [Ipsc2015]Humble Captains

第一问： 网络流，这并没有什么问题

第二问： 阿丽和桃子的游戏，这并没有什么问题

总之是傻逼了

?
code:
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
//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
    int ret=0,f=1; char ch;
    for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
        if (ch=='-') f=-f;
    for (;'0'<=ch && ch<='9';ch=getchar())
        ret=ret*10+ch-'0';
    return ret*f;
}
const int N = 210;
struct edge{
    int to,flow;
    edge(int to=0,int flow=0): to(to),flow(flow){}
}e[N*N*2];
int d[N],f[N*N*2],x[N],n,m,cnt,q[N];
vector<int>g[N];
bitset<N*N>A;
inline void connect(int a,int b,int f){
    e[cnt]=edge(b,f);
    g[a].push_back(cnt++);
    x[a]++;
    e[cnt]=edge(a,f);
    g[b].push_back(cnt++);
    x[b]++;
}
int s=1,t=2;
inline int bfs()
{
    int head=0,tail=1,u,v;
    for (int i=1;i<=n;i++) d[i]=0;
    d[s]=1; q[1]=s;
    while (head<tail){
        u=q[++head];
        for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){
            if (e[*it].flow && !d[e[*it].to]){
                q[++tail]=e[*it].to;
                d[e[*it].to]=d[u]+1;
            }
        }
    }
    return d[t];
}
inline int dfs(int x,int flow){
    if (x==t || flow==0) return flow;
    int totflow=0,f;
    for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
        if (e[*it].flow && d[e[*it].to]==d[x]+1){
            f=dfs(e[*it].to,min(flow,e[*it].flow));
            flow-=f; totflow+=f;
            e[*it].flow-=f; e[(*it)^1].flow+=f;
            if (flow==0) return totflow;
        }
    }
    if (flow) d[x]=-1;
    return totflow;
}
inline void work()
{
    int ans1=0,ans2=0;
    n=read(); m=read();
    cnt=0;
    for (int i=1;i<=n;i++){
        g[i].clear();
        x[i]=0;
    }
    int cE=m;
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        if (x+y==3) cE--;
        else connect(x,y,1);
    }
    for (int i=0;i<=m*2;i++) A[i]=0;
    A[x[1]]=1;
    while (bfs()) ans1+=dfs(s,INT_MAX);
    printf("%d ",cE-ans1);
    for (int i=3;i<=n;i++){
        A=(A<<x[i]|A);
    }
    for (int i=0;i<=cE;i++){
        if (A[cE+i]==1 || A[cE-i]==1){
            printf("%d\n",i);
            break;
        }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    int T=read();
    while (T--) work();
    return 0;
}

 

Category: 未分类 | Tags: bzoj ipsc 网络流 贪心

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com