2019DX#2

太过爱你忘了你带给我的痛 2021-11-10 03:04 309阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td>Solved</td> 
   <td>Pro.ID</td> 
   <td>Title</td> 
   <td>Ratio(Accepted / Submitted)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1001</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&amp;cid=849" rel="nofollow">Another Chess Problem</a></td> 
   <td>8.33%(1/12)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1002</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&amp;cid=849" rel="nofollow">Beauty Of Unimodal Sequence</a></td> 
   <td>19.07%(74/388)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1003</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&amp;cid=849" rel="nofollow">Coefficient</a></td> 
   <td>6.76%(5/74)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1004</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&amp;cid=849" rel="nofollow">Double Tree</a></td> 
   <td>0.00%(0/20)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;<img src="http://acm.hdu.edu.cn/images/ac.gif" alt="" width="16" height="16"></td> 
   <td>1005</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1005&amp;cid=849" rel="nofollow">Everything Is Generated In Equal Probability</a></td> 
   <td>43.14%(516/1196)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1006</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&amp;cid=849" rel="nofollow">Fantastic Magic Cube</a></td> 
   <td>41.82%(23/55)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1007</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&amp;cid=849" rel="nofollow">Game</a></td> 
   <td>3.85%(4/104)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;?</td> 
   <td>1008</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&amp;cid=849" rel="nofollow">Harmonious Army　</a> 　　网络流最小割模型<a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&amp;cid=849" rel="nofollow"><br></a></td> 
   <td>19.93%(54/271)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1009</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&amp;cid=849" rel="nofollow">I Love Palindrome String</a></td> 
   <td>17.03%(101/593)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;<img src="http://acm.hdu.edu.cn/images/ac.gif" alt="" width="16" height="16"></td> 
   <td>1010</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&amp;cid=849" rel="nofollow">Just Skip The Problem</a></td> 
   <td>31.67%(1105/3489)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;<img src="http://acm.hdu.edu.cn/images/ac.gif" alt="" width="16" height="16"></td> 
   <td>1011</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&amp;cid=849" rel="nofollow">Keen On Everything But Triangle</a></td> 
   <td>11.26%(523/4646)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1012</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1012&amp;cid=849" rel="nofollow">Longest Subarray</a></td> 
   <td>11.84%(105/887)<br><br></td> 
  </tr> 
 </tbody> 
</table>

# 1008 Harmonious Army #

## 题意 ##

有n个士兵，要求分成两组，然后就是某些对士兵间有关系，对于一对关系（u,v,a,b,c），如果u,v在同在Warrior，能得到a，如果同在Mage，则得到c，如果在不同组，则得到b，

问得到最大值是多少。

## 思路 ##

网络流，自己还是要多练练网络流的题目。

最小割的模型，因为一个士兵要么在Mage，要么在Warrior。

所以我们把Mage当作源点，把Warrior当作汇点。

有关系的两点，有三种关系A，B，C，我们考虑割掉边的不同组合，重新计算出每条边的流量。

最后拿总流量减去最小割即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    #define pb push_back
    #define fi first
    #define se second
    #define debug(x) cerr<<#x << " := " << x << endl;
    #define bug cerr<<"-----------------------"<<endl;
    #define FOR(a, b, c) for(int a = b; a <= c; ++ a)
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    
    
    template<class T> void _R(T &x) { cin >> x; }
    void _R(int &x) { scanf("%d", &x); }
    void _R(ll &x) { scanf("%lld", &x); }
    void _R(double &x) { scanf("%lf", &x); }
    void _R(char &x) { scanf(" %c", &x); }
    void _R(char *x) { scanf("%s", x); }
    void R() {}
    template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
    
    
    template<typename T>
    inline T read(T&x){
        x=0;int f=0;char ch=getchar();
        while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
        while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
        return x=f?-x:x;
    }
    
    const int inf = 0x3f3f3f3f;
    const ll inff = 0x3f3f3f3f3f3f3f3f;
    const int mod = 998244353;
    
    /**********showtime************/
        
                const int maxm = 5e5+9;
                const int maxn = 509;
                struct Edge{
                    int v,w;
                    int nxt;
                }edge[maxm];
                int gtot = 0, head[maxn];
                void addedge(int u,int v, int w){
                    edge[gtot].v = v;
                    edge[gtot].w = w;
                    edge[gtot].nxt = head[u];
                    head[u] = gtot++;
    
                    edge[gtot].v = u;
                    edge[gtot].w = 0;
                    edge[gtot].nxt = head[v];
                    head[v] = gtot++;
                }
    
                int dis[maxn],cur[maxn];
                bool bfs(int s,int t) {
                    for(int i=s; i<=t; i++) {
                        dis[i] = inf;
                        cur[i] = head[i];
                    }
                    queue<int>que;
                    dis[s] = 0;
                    que.push(s);
                    while(!que.empty()){
    
                        int u = que.front(); que.pop();
                        for(int i=head[u]; ~i; i = edge[i].nxt){
                            int v = edge[i].v;
                            int w = edge[i].w;
                            if(w > 0 && dis[v] > dis[u] + 1 ) {
                                dis[v] = dis[u] + 1;
                                que.push(v);
                            }
                        }
                    }
                    return dis[t] < inf;
                }
                ll dfs(int u, int t, ll maxflow) {
                    if(u == t || maxflow == 0) return maxflow;
                    for(int i=cur[u]; ~i; i=edge[i].nxt){
                        cur[u] = i;
                        int v = edge[i].v;
                        int w = edge[i].w;
                        if(w > 0 && dis[v] == dis[u] + 1){
                            int f = dfs(v, t, min(maxflow, 1ll*w));
                            if(f> 0) {
                                edge[i].w -= f;
                                edge[i ^ 1].w += f;
                                return f;
                            }
                        }
                    }
                    return 0;
                }
                ll dinic(int s,int t) {
                    ll flow = 0;
                    while(bfs(s, t)) {
                        while(ll f = dfs(s, t, inff)) flow += f;
                    }
                    return flow;
                }
    int main(){
                int n,m;
                while(~scanf("%d%d", &n, &m)){
                    gtot = 0;
                    for(int i=0; i<=n+1; i++) head[i]= -1;
    
                    ll sum = 0;
                    int s = 0, t = n+1;
                    for(int i=1; i<=m; i++) {
                        int u,v,a,b,c;
                        scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);
                        a = a * 2;
                        b = b * 2;
                        c = c * 2;
                        sum += (a + b + c);
                        addedge(s, u, (b + c) / 2);
                        addedge(s, v, (b + c) / 2);
                        addedge(u, t, (a + b) / 2);
                        addedge(v, t, (a + b) / 2);
                        addedge(u, v, (a + c) / 2 - b);
                        addedge(v, u, (a + c) / 2 - b);
                    }
                    printf("%lld\n", (sum - dinic(s, t)) / 2);
                }
                return 0;
    }

转载于:https://www.cnblogs.com/ckxkexing/p/11241597.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/0ba5b3b380c04d0b92a47c024b509d32.png