牛客&科大讯飞杯&SHU、L动物森友会【二分】【网络流】

思路

　　比赛的时候读了下感觉是网络流，还口胡了正解

　　然而打歪了？？？

　　一直以为只能用一周做完任务，还在想只有7天枚举不就好了还写啥Dinic，真是图样啊

　　一开始做的是动态建图跑最大流枚举悔边（毕竟一开始以为只能用一周来做任务

　　建立源点，连接周几，容量为e，然后对每个可以在这一天上开展的任务连边，容量为inf，最后把任务连汇点，容量为 c [ i ]，对于天数动态加边建立一张图跑最大流

　　其实这样做反而复杂化了。

　　如果不是在一周内做完的话，实际上就是一个求能满足整张图的跑满时边的容量的最大值最小的问题

　　那么很容易想到二分法

　　因为容量实际上是和天数相关的，而我们最终也是在求这个天数

　　所以考虑二分天数

　　天数和流量的关系是什么呢？

　　不难想到，从 0 周开始算，例如周一的容量就是本周是第 i 周 * e + 这周是否已经过了周一 * e

　　以此类推，可以以此表示出不同天数的从 S 到周几的容量

　　然后跑DINIC，如果当前容量可以跑满的话，说明当前天数一定是 >= 最少天数的

　　以此作为 check 来更新 mid 和 ans 来求最少天数即可

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5  
  6 using namespace std;
  7 typedef long long LL;
  8  
  9 const LL inf = 1e14;
 10  
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17  
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29  
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47  
 48 const int maxn = 200007;
 49  
 50 int n, m;
 51 int s, t;
 52  
 53 struct edge{
 54     int from,to;
 55     LL cap,flow;
 56 };
 57  
 58 map<int, int> vis;
 59  
 60 struct DINIC {
 61     int head[maxn << 1], nxt[maxn << 1];
 62     int edge[maxn << 1], cnt;
 63     LL cap[maxn << 1], depth[maxn << 1];
 64  
 65     void init() {
 66         cnt = 1;
 67         memset(head, 0, sizeof(head));
 68         memset(depth, 0, sizeof(depth));
 69         memset(cap, 0, sizeof(cap));
 70     }
 71  
 72     void BuildGraph(int u, int v, LL w) {
 73         ++cnt;
 74         edge[cnt] = v;
 75         nxt[cnt] = head[u];
 76         cap[cnt] = w;
 77         head[u] = cnt;
 78  
 79         ++cnt;
 80         edge[cnt] = u;
 81         nxt[cnt] = head[v];
 82         cap[cnt] = 0;
 83         head[v] = cnt;
 84     }
 85  
 86     queue<int> q;
 87  
 88     bool bfs() {
 89         memset(depth, 0, sizeof(depth));
 90         depth[s] = 1;
 91         q.push(s);
 92         while(!q.empty()) {
 93             int u = q.front();
 94             q.pop();
 95             for ( int i = head[u]; i; i = nxt[i] ) {
 96                 int v = edge[i];
 97                 if(depth[v]) {
 98                     continue;
 99                 }
100                 if(cap[i]) {
101                     depth[v] = depth[u] + 1;
102                     q.push(v);
103                 }
104             }
105         }
106         return depth[t];
107     }
108  
109     LL dfs(int u, LL dist) {
110         if(u == t) {
111             return dist;
112         }
113         LL flow = 0;
114         for ( int i = head[u]; i && dist; i = nxt[i] ) {
115             if(cap[i] == 0)
116                 continue;
117             int v = edge[i];
118             if(depth[v] != depth[u] + 1) {
119                 continue;
120             }
121             LL res = dfs(v, min(cap[i], dist));
122             cap[i] -= res;
123             cap[i ^ 1] += res;
124             //printf("cap[%d]:%d
",t, cap[t]);
125             dist -= res;
126             flow += res;
127         }
128         return flow;
129     }
130  
131     LL maxflow() {
132         LL ans = 0;
133         while(bfs()) {
134             ans += dfs(s, inf);
135         }
136         return ans;
137     }
138 } dinic;
139  
140 int e;
141 LL c[maxn], mi[maxn];
142 int a[maxn][10];
143 LL tot = 0;
144  
145 void BuildGraph(LL limit) {
146     dinic.init();
147     s = 0, t = n + 8;
148     for ( int i = 1; i <= 7; ++i ) {
149         LL day = limit / 7;
150         if(limit % 7 >= i) {
151             day++;
152         }
153         dinic.BuildGraph(s, i, day * e);
154     }
155     for ( int i = 1; i <= n; ++i ) {
156         for ( int j = 1; j <= mi[i]; ++j ) {
157             dinic.BuildGraph(a[i][j], i + 7, inf);
158         }
159         dinic.BuildGraph(i + 7, t, c[i]);
160     }
161 }
162  
163 bool check(LL mid) {
164     if(e * mid < tot) {
165         return false;
166     }
167     BuildGraph(mid);
168     LL temp = dinic.maxflow();
169     //if(temp < 100) dbg(temp);
170     return temp >= tot;
171 }
172  
173 int main()
174 {
175     //freopen("data.txt", "r", stdin);
176     dinic.init();
177     read(n); read(e);
178     s = 0, t = n + 8;
179     for ( int i = 1; i <= n; ++i ) {
180         read(c[i]); read(mi[i]);
181         tot += c[i];
182         for ( int j = 1; j <= mi[i]; ++j ) {
183             read(a[i][j]);
184         }
185     }
186     LL l = 1, r = tot / e, mid, ans = 0;
187     while(l <= r) {
188         mid = (l + r) >> 1;
189         if(check(mid)) {
190             r = mid - 1;
191             ans = mid;
192         }
193         else {
194             l = mid + 1;
195         }
196     }
197     cout << ans << endl;
198     return 0;
199 }

View Code

#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)
 
using namespace std;
typedef long long LL;
 
const LL inf = 1e14;
 
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
 
namespace _buff {
    const size_t BUFF = 1 << 19;
    char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
    char getc() {
        if (ib == ie) {
            ib = ibuf;
            ie = ibuf + fread(ibuf, 1, BUFF, stdin);
        }
        return ib == ie ? -1 : *ib++;
    }
}
 
int qread() {
    using namespace _buff;
    int ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}
 
const int maxn = 200007;
 
int n, m;
int s, t;
 
struct edge{
    int from,to;
    LL cap,flow;
};
 
map<int, int> vis;
 
struct DINIC {
    int head[maxn << 1], nxt[maxn << 1];
    int edge[maxn << 1], cnt;
    LL cap[maxn << 1], depth[maxn << 1];
 
    void init() {
        cnt = 1;
        memset(head, 0, sizeof(head));
        memset(depth, 0, sizeof(depth));
        memset(cap, 0, sizeof(cap));
    }
 
    void BuildGraph(int u, int v, LL w) {
        ++cnt;
        edge[cnt] = v;
        nxt[cnt] = head[u];
        cap[cnt] = w;
        head[u] = cnt;
 
        ++cnt;
        edge[cnt] = u;
        nxt[cnt] = head[v];
        cap[cnt] = 0;
        head[v] = cnt;
    }
 
    queue<int> q;
 
    bool bfs() {
        memset(depth, 0, sizeof(depth));
        depth[s] = 1;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for ( int i = head[u]; i; i = nxt[i] ) {
                int v = edge[i];
                if(depth[v]) {
                    continue;
                }
                if(cap[i]) {
                    depth[v] = depth[u] + 1;
                    q.push(v);
                }
            }
        }
        return depth[t];
    }
 
    LL dfs(int u, LL dist) {
        if(u == t) {
            return dist;
        }
        LL flow = 0;
        for ( int i = head[u]; i && dist; i = nxt[i] ) {
            if(cap[i] == 0)
                continue;
            int v = edge[i];
            if(depth[v] != depth[u] + 1) {
                continue;
            }
            LL res = dfs(v, min(cap[i], dist));
            cap[i] -= res;
            cap[i ^ 1] += res;
            //printf("cap[%d]:%d
",t, cap[t]);
            dist -= res;
            flow += res;
        }
        return flow;
    }
 
    LL maxflow() {
        LL ans = 0;
        while(bfs()) {
            ans += dfs(s, inf);
        }
        return ans;
    }
} dinic;
 
int e;
LL c[maxn], mi[maxn];
int a[maxn][10];
LL tot = 0;
 
void BuildGraph(LL limit) {
    dinic.init();
    s = 0, t = n + 8;
    for ( int i = 1; i <= 7; ++i ) {
        LL day = limit / 7;
        if(limit % 7 >= i) {
            day++;
        }
        dinic.BuildGraph(s, i, day * e);
    }
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 1; j <= mi[i]; ++j ) {
            dinic.BuildGraph(a[i][j], i + 7, inf);
        }
        dinic.BuildGraph(i + 7, t, c[i]);
    }
}
 
bool check(LL mid) {
    if(e * mid < tot) {
        return false;
    }
    BuildGraph(mid);
    LL temp = dinic.maxflow();
    //if(temp < 100) dbg(temp);
    return temp >= tot;
}
 
int main()
{
    //freopen("data.txt", "r", stdin);
    dinic.init();
    read(n); read(e);
    s = 0, t = n + 8;
    for ( int i = 1; i <= n; ++i ) {
        read(c[i]); read(mi[i]);
        tot += c[i];
        for ( int j = 1; j <= mi[i]; ++j ) {
            read(a[i][j]);
        }
    }
    LL l = 1, r = tot / e, mid, ans = 0;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}