第六周 2.21-2.27

只有一周了QAQ

2.21

其实Tarjan的时候搞一搞，就O（n+m）了吖。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <vector>
  4 using namespace std;
  5 typedef long long LL;
  6 typedef pair<int, int> pii;
  7 const int maxn = 1e5 + 10;
  8 vector<pii> q[maxn];
  9 double ans[maxn];
 10 
 11 //Tree
 12 int cnt, h[maxn];
 13 struct edge
 14 {
 15     int to, pre;
 16 } e[maxn<<1];
 17 
 18 void add(int from, int to)
 19 {
 20     cnt++;
 21     e[cnt].pre = h[from];
 22     e[cnt].to = to;
 23     h[from] = cnt;
 24 }
 25 
 26 //TreeDP
 27 LL dis[maxn], fdis[maxn];
 28 int sz[maxn], fsz[maxn], dep[maxn];
 29 void dfs1(int p, int d)
 30 {
 31     sz[p] = 1, dep[p] = d;
 32     for(int i = h[p]; i; i = e[i].pre)
 33     {
 34         int to = e[i].to;
 35         if(dep[to]) continue;
 36         dfs1(to, d + 1);
 37         sz[p] += sz[to];
 38         dis[p] += dis[to] + sz[to];
 39     }
 40 }
 41 
 42 //Tarjan
 43 int fa[maxn], vis[maxn], cur[maxn];
 44 int Find(int x)
 45 {
 46     return fa[x] == x ? x : fa[x] = Find(fa[x]);
 47 }
 48 
 49 void dfs2(int p, int f)
 50 {
 51     fa[p] = p, vis[p] = 2;
 52     if(p != 1)
 53     {
 54         fsz[p] = fsz[f] + sz[f] - sz[p];
 55         fdis[p] = fdis[f] + dis[f] - dis[p] - sz[p] + fsz[p];
 56     }
 57     for(int i = h[p]; i; i = e[i].pre)
 58     {
 59         int to = e[i].to;
 60         if(to == f) continue;
 61         cur[p] = to;
 62         dfs2(to, p);
 63         fa[to] = p;
 64     }
 65     vis[p] = 1;
 66     int qsz = q[p].size();
 67     for(int i = 0; i < qsz; i++)
 68     {
 69         int to = q[p][i].first, id = q[p][i].second;
 70         if(!vis[to]) continue;
 71         int anc = Find(to);
 72         if(anc == to)
 73         {
 74             LL d = dep[p] - dep[to] + 1;
 75             ans[id] = (1.0 * dis[p] * fsz[cur[to]] + 1.0 * (fdis[cur[to]] - (LL)fsz[cur[to]]) * sz[p]) / sz[p] / fsz[cur[to]] + d;
 76         }
 77         else if(vis[p] == 1 && anc != p)
 78         {
 79             LL d = dep[p] + dep[to] - dep[anc] - dep[anc] + 1;
 80             ans[id] = (1.0 * dis[p] * sz[to] + 1.0 * dis[to] * sz[p]) / sz[p] / sz[to] + d;
 81         }
 82     }
 83     return;
 84 }
 85 
 86 int main(void)
 87 {
 88     int n, m;
 89     scanf("%d %d", &n, &m);
 90     for(int i = 1; i < n; i++)
 91     {
 92         int u, v;
 93         scanf("%d %d", &u, &v);
 94         add(u, v), add(v, u);
 95     }
 96     for(int i = 0; i < m; i++)
 97     {
 98         int u, v;
 99         scanf("%d %d", &u, &v);
100         q[u].push_back(pii(v, i));
101         q[v].push_back(pii(u, i));
102     }
103     dfs1(1, 1);
104     dfs2(1, 0);
105     for(int i = 0; i < m; i++) printf("%.9f
", ans[i]);
106     return 0;
107 }

Aguin

HDU 3605 Escape

原来是状压阿。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int INF = 1e9;
  8 const int maxn = 2e5 + 10;
  9 int lv[maxn], it[maxn];
 10 int cnt, h[maxn];
 11 
 12 struct edge
 13 {
 14     int to, pre, cap;
 15 } e[maxn<<1];
 16 
 17 void init()
 18 {
 19     memset(h, -1, sizeof(h));
 20     cnt = 0;
 21 }
 22 
 23 void add(int from, int to, int cap)
 24 {
 25     e[cnt].pre = h[from];
 26     e[cnt].to = to;
 27     e[cnt].cap = cap;
 28     h[from] = cnt;
 29     cnt++;
 30 }
 31 
 32 void ad(int from, int to, int cap)
 33 {
 34     add(from, to, cap);
 35     add(to, from, 0);
 36 }
 37 
 38 void bfs(int s)
 39 {
 40     memset(lv, -1, sizeof(lv));
 41     queue<int> q;
 42     lv[s] = 0;
 43     q.push(s);
 44     while(!q.empty())
 45     {
 46         int v = q.front(); q.pop();
 47         for(int i = h[v]; i >= 0; i = e[i].pre)
 48         {
 49             int cap = e[i].cap, to = e[i].to;
 50             if(cap > 0 && lv[to] < 0)
 51             {
 52                 lv[to] = lv[v] + 1;
 53                 q.push(to);
 54             }
 55         }
 56     }
 57 }
 58 
 59 int dfs(int v, int t, int f)
 60 {
 61     if(v == t) return f;
 62     for(int &i = it[v]; i >= 0; i = e[i].pre)
 63     {
 64         int &cap = e[i].cap, to = e[i].to;
 65         if(cap > 0 && lv[v] < lv[to])
 66         {
 67             int d = dfs(to, t, min(f, cap));
 68             if(d > 0)
 69             {
 70                 cap -= d;
 71                 e[i^1].cap += d;
 72                 return d;
 73             }
 74         }
 75     }
 76     return 0;
 77 }
 78 
 79 int Dinic(int s, int t)
 80 {
 81     int flow = 0;
 82     while(1)
 83     {
 84         bfs(s);
 85         if(lv[t] < 0) return flow;
 86         memcpy(it, h, sizeof(it));
 87         int f;
 88         while((f = dfs(s, t, INF)) > 0) flow += f;
 89     }
 90 }
 91 
 92 int peo[1025];
 93 int main(void)
 94 {
 95     int n, m;
 96     while(~scanf("%d %d", &n, &m))
 97     {
 98         init();
 99         memset(peo, 0, sizeof(peo));
100         int S = (1 << m) + m + 1, T = S + 1;
101         for(int i = 1; i <= n; i++)
102         {
103             int tmp = 0;
104             for(int j = 0; j < m; j++)
105             {
106                 int x;
107                 scanf("%d", &x);
108                 tmp += x << j;
109             }
110             peo[tmp]++;
111         }
112         for(int i = 1; i < (1 << m); i++)
113         {
114             if(!peo[i]) continue;
115             ad(S, i, peo[i]);
116             for(int j = 0; j < m; j++)
117                 if(i & (1 << j)) ad(i, (1 << m) + j, INF);
118         }
119         for(int i = 0; i < m; i++)
120         {
121             int x;
122             scanf("%d", &x);
123             ad((1 << m) + i, T, x);
124         }
125         puts(Dinic(S, T) == n ? "YES" : "NO");
126     }
127     return 0;
128 }

Aguin

2.22

HDU 3081 Marriage Match II

还要二分一下。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int INF = 1e9;
  8 const int maxn = 2e5 + 10;
  9 int lv[maxn], it[maxn];
 10 int cnt, h[maxn];
 11 
 12 struct edge
 13 {
 14     int to, pre, cap;
 15 } e[maxn<<1];
 16 
 17 void init()
 18 {
 19     memset(h, -1, sizeof(h));
 20     cnt = 0;
 21 }
 22 
 23 void add(int from, int to, int cap)
 24 {
 25     e[cnt].pre = h[from];
 26     e[cnt].to = to;
 27     e[cnt].cap = cap;
 28     h[from] = cnt;
 29     cnt++;
 30 }
 31 
 32 void ad(int from, int to, int cap)
 33 {
 34     add(from, to, cap);
 35     add(to, from, 0);
 36 }
 37 
 38 void bfs(int s)
 39 {
 40     memset(lv, -1, sizeof(lv));
 41     queue<int> q;
 42     lv[s] = 0;
 43     q.push(s);
 44     while(!q.empty())
 45     {
 46         int v = q.front(); q.pop();
 47         for(int i = h[v]; i >= 0; i = e[i].pre)
 48         {
 49             int cap = e[i].cap, to = e[i].to;
 50             if(cap > 0 && lv[to] < 0)
 51             {
 52                 lv[to] = lv[v] + 1;
 53                 q.push(to);
 54             }
 55         }
 56     }
 57 }
 58 
 59 int dfs(int v, int t, int f)
 60 {
 61     if(v == t) return f;
 62     for(int &i = it[v]; i >= 0; i = e[i].pre)
 63     {
 64         int &cap = e[i].cap, to = e[i].to;
 65         if(cap > 0 && lv[v] < lv[to])
 66         {
 67             int d = dfs(to, t, min(f, cap));
 68             if(d > 0)
 69             {
 70                 cap -= d;
 71                 e[i^1].cap += d;
 72                 return d;
 73             }
 74         }
 75     }
 76     return 0;
 77 }
 78 
 79 int Dinic(int s, int t)
 80 {
 81     int flow = 0;
 82     while(1)
 83     {
 84         bfs(s);
 85         if(lv[t] < 0) return flow;
 86         memcpy(it, h, sizeof(it));
 87         int f;
 88         while((f = dfs(s, t, INF)) > 0) flow += f;
 89     }
 90 }
 91 
 92 int fa[111], r[111];
 93 int Find(int x)
 94 {
 95     return fa[x] == x ? x : fa[x] = Find(fa[x]);
 96 }
 97 
 98 void Union(int x, int y)
 99 {
100     x = Find(x);
101     y = Find(y);
102     if(x != y)
103     {
104         if(r[x] < r[y]) swap(x, y);
105         fa[y] = x;
106         r[x] += r[y];
107     }
108 }
109 
110 int G[111][111];
111 int main(void)
112 {
113     int T;
114     scanf("%d", &T);
115     while(T--)
116     {
117         int n, m, f;
118         scanf("%d %d %d", &n, &m, &f);
119         memset(G, 0, sizeof(G));
120         for(int i = 0; i <= n; i++) fa[i] = i, r[i] = 1;
121         for(int i = 0; i < m; i++)
122         {
123             int u, v;
124             scanf("%d %d", &u, &v);
125             G[u][v] = 1;
126         }
127         for(int i = 0; i < f; i++)
128         {
129             int u, v;
130             scanf("%d %d", &u, &v);
131             Union(u, v);
132         }
133         int S = n + n + 1, T = S + 1;
134         for(int i = 1; i <= n; i++)
135         {
136             int f = Find(i);
137             if(f == i) continue;
138             for(int j = 1; j <= n; j++) G[f][j] |= G[i][j];
139         }
140         int L = 0, R = n, mid;
141         while(L < R)
142         {
143             mid = R - (R - L) / 2;
144             init();
145             for(int i = 1; i <= n; i++) ad(n + i, T, mid);
146             for(int i = 1; i <= n; i++)
147             {
148                 if(Find(i) != i) continue;
149                 ad(S, i, r[i] * mid);
150                 for(int j = 1; j <= n; j++)
151                     if(G[i][j]) ad(i, n + j, r[i]);
152             }
153             if(Dinic(S,T) != mid * n) R = mid - 1;
154             else L = mid;
155         }
156         printf("%d
", L);
157     }
158     return 0;
159 }

Aguin

2.23

TC SRM 682 Div1 300 SmilesTheFriendshipUnicorn

暴力就好了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int maxn = 2e5 + 10;
 7 int ok, cnt, h[2020], vis[2020];
 8 
 9 struct edge
10 {
11     int to, pre;
12 } e[maxn<<1];
13 
14 void add(int from, int to)
15 {
16     cnt++;
17     e[cnt].pre = h[from];
18     e[cnt].to = to;
19     h[from] = cnt;
20 }
21 
22 void init()
23 {
24     cnt = 0;
25     memset(h, 0, sizeof(h));
26 }
27 
28 void DFS(int x, int d)
29 {
30     vis[x] = 1;
31     if(d == 5) {ok = 1; return;}
32     for(int i = h[x]; i; i = e[i].pre)
33     {
34         int to = e[i].to;
35         if(vis[to]) continue;
36         DFS(to, d + 1);
37     }
38     vis[x] = 0;
39     return;
40 }
41 
42 class SmilesTheFriendshipUnicorn
43 {
44 
45 public:
46 
47     string hasFriendshipChain(int N, vector <int> A, vector <int> B)
48     {
49         init();
50         int m = A.size();
51         for(int i = 0; i < m; i++)
52         {
53             add(A[i], B[i]);
54             add(B[i], A[i]);
55         }
56         for(int i = 0; i < N; i++)
57         {
58             ok = 0;
59             memset(vis, 0, sizeof(vis));
60             DFS(i, 1);
61             if(ok) return string("Yay!");
62         }
63         return string(":(");
64     }
65 
66 };

Aguin

TC SRM 682 Div1 450 SuccessfulMerger

判环判成sb也是没誰了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 2e5 + 10;
int cnt, h[55];
int sz[55], leaf[55];
int fa[55], is[55], vis[55];

struct edge
{
    int to, pre;
} e[maxn<<1];

void add(int from, int to)
{
    cnt++;
    e[cnt].pre = h[from];
    e[cnt].to = to;
    h[from] = cnt;
}

void init()
{
    cnt = 0;
    memset(h, 0, sizeof(h));
    memset(is, 0, sizeof(is));
    memset(fa, -1, sizeof(fa));
    memset(vis, 0, sizeof(vis));
}

void DFS(int x, int f)
{
    vis[x] = 2;
    if(fa[x] != -1)
    {
        int p = f;
        while(p != x)
        {
            is[p] = 1;
            p = fa[p];
        }
        is[x] = is[f] = 1;
        return;
    }
    fa[x] = f;
    for(int i = h[x]; i; i = e[i].pre)
    {
        int to = e[i].to;
        if(to == f || vis[to] == 1) continue;
        DFS(to, x);
    }
    vis[x] = 1;
}

void DFS2(int x, int f)
{
    sz[x] = 1;
    int tot = 0;
    for(int i = h[x]; i; i = e[i].pre)
    {
        int to = e[i].to;
        if(to == f || is[to]) continue;
        tot++;
        DFS2(to, x);
        sz[x] += sz[to];
        leaf[x] += leaf[to];
    }
    if(tot == 0) leaf[x] = 1;
    return;
}

class SuccessfulMerger
{

public:

    int minimumMergers(vector <int> road)
    {
        init();
        int N = road.size(), two = 0;
        for(int i = 0; i < N; i++)
        {
            add(i, road[i]);
            add(road[i], i);
            if(i == road[road[i]])
            {
                two = 1;
                is[i] = is[road[i]] = 1;
            }
        }
        if(!two) DFS(0, -2);
        int ans = 0, r = 0, one = 0;
        for(int i = 0; i < N; i++)
        {
            if(!is[i]) continue;
            r++;
            DFS2(i, -1);
            if(sz[i] == 1) one = 1;
            else ans += sz[i] - leaf[i] - 1;
        }
        return ans + r - 1 - one;
    }

};

Aguin

HDU 3416 Marriage Match IV

SPFA跑跑Dinic跑跑。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e5 + 10;
const int INF = 1e9;
int lv[1111], it[1111];
int dist[1111], vis[1111];
int cnt, h[1111];

struct edge
{
    int to, pre, cap;
} e[maxn<<1];

void init()
{
    memset(h, -1, sizeof(h));
    cnt = 0;
}

void add(int from, int to, int cap)
{
    e[cnt].pre = h[from];
    e[cnt].to = to;
    e[cnt].cap = cap;
    h[from] = cnt;
    cnt++;
}

void ad(int from, int to, int cap)
{
    add(from, to, cap);
    add(to, from, 0);
}

vector<int> ve[1111];
void SPFA(int s)
{
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < 1111; i++) dist[i] = INF;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        vis[v] = 0;
        for(int i = h[v]; i >= 0; i = e[i].pre)
        {
            int to = e[i].to, cost = e[i].cap;
            if(dist[to] > dist[v] + cost)
            {
                ve[to].clear();
                ve[to].push_back(v);
                dist[to] = dist[v] + cost;
                if(!vis[to]) q.push(to);
                vis[to] = 1;
            }
            else if(dist[to] == dist[v] + cost)
            {
                ve[to].push_back(v);
                if(!vis[to]) q.push(to);
                vis[to] = 1;
            }
        }
    }
}

void bfs(int s)
{
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    lv[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        for(int i = h[v]; i >= 0; i = e[i].pre)
        {
            int cap = e[i].cap, to = e[i].to;
            if(cap > 0 && lv[to] < 0)
            {
                lv[to] = lv[v] + 1;
                q.push(to);
            }
        }
    }
}

int dfs(int v, int t, int f)
{
    if(v == t) return f;
    for(int &i = it[v]; i >= 0; i = e[i].pre)
    {
        int &cap = e[i].cap, to = e[i].to;
        if(cap > 0 && lv[v] < lv[to])
        {
            int d = dfs(to, t, min(f, cap));
            if(d > 0)
            {
                cap -= d;
                e[i^1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s, int t)
{
    int flow = 0;
    while(1)
    {
        bfs(s);
        if(lv[t] < 0) return flow;
        memcpy(it, h, sizeof(it));
        int f;
        while((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        init();
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            add(a, b, c);
        }
        int S, T;
        scanf("%d %d", &S, &T);
        SPFA(S);
        init();
        queue<int> q;
        q.push(T);
        memset(vis, 0, sizeof(vis));
        while(!q.empty())
        {
            int v = q.front(); q.pop();
            int sz = ve[v].size();
            for(int i = 0; i < sz; i++)
            {
                int u = ve[v][i];
                ad(u, v, 1);
                if(vis[u]) continue;
                q.push(u);
                vis[u] = 1;
            }
        }
        printf("%d
", Dinic(S, T));
    }
    return 0;
}

Aguin

2.24-2.27

什么都没干。