2020杭电暑期多校第四场

Author Avatar
MorphLing 8月 03, 2020

1004.Deliver-the-Cake

标签：思维、最短路
把所有M的点拆成L和R两个点，连边的时候如果两个点属性相同边值就为w，属性不同就设为w+x

一开始想直接在dijsktra板子上面改，改来改去发现自己晕了。最后老老实实重新写了个拆点连边的才过的。这个故事告诉我们能在建模上完成的操作就不要靠改板子来实现了。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e5+5;
const ll INF=1e18;

struct Edge{
    ll to,val;
};

vector<Edge>G[N];

struct Node{
    ll dis;
    int key;
    friend bool operator <(const Node &x,const Node &y)
    {
        return x.dis>y.dis;
    }
};

int n,m,s,t,x;

ll dis[N];

bool vis[N];

void dijkstra()
{
    priority_queue<Node>Q;
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n*2;i++) dis[i]=INF;
    dis[s]=0;
    Q.push({0,s});
    while(!Q.empty())
    {
        Node top=Q.top();
        Q.pop();
        int now=top.key;
        if (vis[now]) continue;
        vis[now]=1;
        for (int i=0;i<G[now].size();i++)
        {
            int to=G[now][i].to;
            if (dis[to]>dis[now]+G[now][i].val)
            {
                dis[to]=dis[now]+G[now][i].val;
                if (!vis[to]) Q.push({dis[to],to});
            }
        }
    }
}
char ss[N];
int tag[N];
int T,u,v,w;

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>s>>t>>x;
        scanf("%s",ss+1);
        for (int i=1;i<=n*2;i++) G[i].clear();
        for (int i=1;i<=n;i++)
        {
            if (ss[i]=='L') tag[i]=0;
            if (ss[i]=='R') tag[i]=1;
            if (ss[i]=='M') tag[i]=2;
        }
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            if (tag[u]!=2 && tag[v]!=2)
            {
                G[n*tag[u]+u].push_back({n*tag[v]+v,w+(tag[u]==tag[v]?0:x)});
                G[n*tag[v]+v].push_back({n*tag[u]+u,w+(tag[u]==tag[v]?0:x)});
            }
            if (tag[u]==2 && tag[v]!=2)
            {
                G[u].push_back({n*tag[v]+v,w+(tag[v]==0?0:x)});
                G[n+u].push_back({n*tag[v]+v,w+(tag[v]==1?0:x)});
                G[n*tag[v]+v].push_back({u,w+(tag[v]==0?0:x)});
                G[n*tag[v]+v].push_back({n+u,w+(tag[v]==1?0:x)});
            }
            if (tag[v]==2 && tag[u]!=2)
            {
                G[v].push_back({n*tag[u]+u,w+(tag[u]==0?0:x)});
                G[n+v].push_back({n*tag[u]+u,w+(tag[u]==1?0:x)});
                G[n*tag[u]+u].push_back({v,w+(tag[u]==0?0:x)});
                G[n*tag[u]+u].push_back({n+v,w+(tag[u]==1?0:x)});
            }
            if (tag[u]==2 && tag[v]==2)
            {
                G[u].push_back({v,w});
                G[u].push_back({n+v,w+x});
                G[v].push_back({u,w});
                G[v].push_back({n+u,w+x});
                G[n+u].push_back({v,w+x});
                G[n+u].push_back({n+v,w});
                G[n+v].push_back({u,w+x});
                G[n+v].push_back({n+u,w});
            }
        }
        if (tag[s]!=2)
        {
            s=s+tag[s]*n;
            dijkstra();
            if (tag[t]!=2)
            {
                printf("%lld\n",dis[t+tag[t]*n]);
            }
            else
            {
                printf("%lld\n",min(dis[t],dis[t+n]));
            }
        }
        else
        {
            ll ans=INF;
            s=s;
            dijkstra();
            if (tag[t]!=2)
            {
                ans=min(ans,dis[t+tag[t]*n]);
            }
            else
            {
                ans=min(ans,min(dis[t],dis[n+t]));
            }
            s=s+n;
            dijkstra();
            if (tag[t]!=2)
            {
                ans=min(ans,dis[t+tag[t]*n]);
            }
            else
            {
                ans=min(ans,min(dis[t],dis[n+t]));
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

1007.Go-Running

标签：二分图最小点覆盖（最小点覆盖=最大匹配）

非常非常值得重点关注的一道题。。通过观察可以发现，所有x+t相同或者x-t相同的点都可以通过一次操作来覆盖。也就是可以将x+t和x-t视作一个物品的两个属性，一次操作可以消去某一属性相同的若干个物品，问最少需要多少次操作。

再把每个属性值视作一个点，把每个物品视作一条边，左右端点分别连在对应的属性点上，就转化成了一个二分图最小点覆盖的问题。

一个必须掌握（至少要记住）的结论是：二分图最小点覆盖=最大匹配

二分图最大匹配的König定理及其证明

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e5+5;

int T,n,u,v;

ll s,t,dep[N];

int _cur[N];

bool used[N];

struct Edge{int to;ll v;int rev;};

vector<Edge>G[N];

void addEdge(int x,int y,ll v)
{
    G[x].push_back((Edge){y,v,(int)G[y].size()});
    G[y].push_back((Edge){x,0,(int)G[x].size()-1});
}
bool bfs()
{

    memset(used,0,sizeof(used));
    dep[s]=1,used[s]=1;
    queue<int>L;
    L.push(s);
    while(!L.empty())
    {
        int cur=L.front();
        L.pop();
        for (int i=0;i<G[cur].size();i++)
        {
            Edge &e=G[cur][i];
            if (!used[e.to] && e.v>0)
            {
                dep[e.to]=dep[cur]+1;
                used[e.to]=1;
                L.push(e.to);
            }
        }
    }
    if (used[t]) return true;
    else return false;
}
ll dfs(int c,ll flow)
{
    if (c==t) return flow;
    if (flow==0) return flow;
    ll ret=0,f;
    for (int &i=_cur[c];i<G[c].size();i++)
    {
        Edge &e=G[c][i];
        if (dep[e.to]==dep[c]+1 && (f=dfs(e.to,min(flow,e.v)))>0)
        {
            ret+=f;
            flow-=f;
            e.v-=f;
            G[e.to][e.rev].v+=f;
            if (flow==0) break;
        }
    }
    return ret;
}
ll Dinic()
{
    ll ans=0;
    while(bfs())
    {
        memset(_cur,0,sizeof(_cur));
        ans+=dfs(s,1ll*100*INT_MAX);
    }
    return ans;
}

void solve()
{
    cin>>n;
    map<int,int>sum,gap;
    int sum_cnt,gap_cnt;
    sum_cnt=gap_cnt=0;
    s=0,t=2*n+1;
    for (int i=0;i<=2*n+1;i++) G[i].clear();
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&u,&v);
        if (sum[u+v]==0) sum[u+v]=++sum_cnt;
        if (gap[u-v]==0) gap[u-v]=++gap_cnt;
        addEdge(sum[u+v],n+gap[u-v],1);
    }
    for (auto x:sum) addEdge(s,x.second,1);
    for (auto x:gap) addEdge(n+x.second,t,1);
    printf("%d\n",Dinic());
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

1003.Contest-of-Rope-Pulling

标签：01背包，随机优化

把第二组的数视作(-wi,vi)，要做的就是取出若干个数，使得$\sum w$为0，且$\sum v$尽可能大。很明显能考虑用01背包解决这个问题，但是由于时间复杂度为$O((n+m)^2·max\{w_i\})$，好像又不太可做的样子。考虑到$\sum w$最大取到$10^6$，那么有没有办法把需要用考虑的上界降下来呢？答案是把n+m个数顺序随机打乱之后，我们只要考虑到上界为$limit=\sqrt{n+m}·max\{w_i\}$的情况即可，因为超出这个范围的解概率是极低的，具体的概率大概是$10^{-7}$，详见题解的证明。

涉及知识盲区的一道题，完全想不到通过随机来优化dp。。以后还是要多练一点随机处理的题目

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e3+5,INF=0x3f3f3f3f3f,M=2e6+5;

mt19937 rnd(time(NULL));

int T,n,m;

struct Node{
    int w,v,ty;
    ll seed;
};

Node A[N];

ll f[M],g[M];

ll query(int x)
{
    if (x>=0) return f[x];
    else return g[-x];
}

void modify(int x,ll v)
{
    if (x>=0) f[x]=v;
    else g[-x]=v;
}

void solve()
{
    cin>>n>>m;
    for (int i=1;i<=n+m;i++)
    {
        scanf("%d%d",&A[i].w,&A[i].v);
        A[i].ty=i<=n;
        A[i].seed=rnd();
    }
    sort(A+1,A+1+n+m,[&](Node a,Node b){return a.seed<b.seed;});
    int limit=sqrt(n+m)*1000;
    for (int i=0;i<=limit;i++) f[i]=g[i]=-INF;
    f[0]=0;
    for (int i=1;i<=n+m;i++)
    {
        if (A[i].ty==1)
        {
            for (int j=limit;j>=-limit;j--)
            {
                if (j-A[i].w<-limit) continue;
                ll ask=query(j-A[i].w);
                if (ask==-INF) continue;
                if (ask+A[i].v>query(j))
                    modify(j,ask+A[i].v);
            }
        }
        else
        {
            for (int j=-limit;j<=limit;j++)
            {
                if (j+A[i].w>limit) continue;
                ll ask=query(j+A[i].w);
                if (ask==-INF) continue;
                if (ask+A[i].v>query(j))
                    modify(j,ask+A[i].v);
            }
        }
    }
    printf("%lld\n",f[0]);
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}