语文是OI的考察范围

懵逼的 题目

传送至 Luogu

扯淡的 题解

这大概是最水的一道紫题了吧…难度虚高@丁虚高

大概题目比较难懂 或者我语文太烂
题目就是说: 一些试卷, 每张试卷都可以归到特定的组里面, (一张试卷只能用一次), 每个组都有特定的大小(即一个组需要恰好有这么多的试卷归在里面), 问如何完成…

把试卷放在左边, 属性放在右边…就是一个很简单的二分图…
连边…

  • s向所有的试卷都连一条cap = 1的边, 代表每道题都只能选一遍
  • 所有的试卷向他所拥有的属性连一条cap = 1的边, 代表选了这道题, 可以归到他有的这些属性里的任意一个
  • 所有的属性向t连一条cap = 属性需要的题目数量的边, 代表一个属性需要有这么多的题

跑最大流, 如果答案比m小, 无解, 否则输出方案

没了…是不是很简单…?

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000 + 5)
#define MAXM (4000 + 5)
#define INF (0x7ffffff)
#define MAXT (1000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) (((a - 1) ^ 1) + 1)
#define bh(a) ((a) + MAXT)
#define ubh(a) ((a) - MAXT)
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
    int cap;
    int flow;
    edg(){}
    edg(int a, int b, int c, int d, int e): from(a), to(b), next(c), cap(d), flow(e){}
}b[MAXM << 1];
int cntb;
int g[MAXN];

int dis[MAXN];

int n;
int kn;
int m;
int ans;
void adn(int, int, int);
void init();
void solve();
int dinic(int, int);
bool bfs();
void print();
int main(int argc, char const *argv[])
{
    init();
    solve();
    if (ans ^ m)
    {
        puts("No Solution!");
        return 0;
    }
    print();
    return 0;
}
void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap, 0);
    g[from] = cntb;
}
void init()
{
    scanf("%d%d", &kn, &n);
    for (int i = 1; i <= kn; i++)
    {
        int srx;
        scanf("%d", &srx);
        m += srx;
        adn(bh(i), t, srx);
        adn(t, bh(i), 0);
    }
    for (int i = 1; i <= n; i++)
    {
        adn(s, i, 1);
        adn(i, 1, 0);
        int srn;
        scanf("%d", &srn);
        for (int j = 1; j <= srn; j++)
        {
            int srx;
            scanf("%d", &srx);
            adn(i, bh(srx), 1);
            adn(bh(srx), i, 0);
        }
    }
}
void solve()
{
    while (bfs())
    {
        int zl = dinic(s, INF);
        ans += zl;
    }
}
bool bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (b[i].cap > b[i].flow && !dis[b[i].to])
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
int dinic(int dq, int maxf)
{
    if (dq == t || (!maxf))
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
            maxf -= zl;
            re += zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }    
    }
    return re;
}
void print()
{
    vector<int> out[MAXT];
    for (int i = 0; i <= cntb; i++)
    {
        if (b[i].cap == b[i].flow && b[i].cap > 0 && b[i].to > MAXT && b[i].from <= MAXT)
        {
            out[ubh(b[i].to)].push_back(b[i].from);
        }
    }
    for (int i = 1; i <= kn; i++)
    {
        printf("%d: ", i);
        for (int j = 0; j < out[i].size(); j++)
        {
            printf("%d ", out[i][j]);
        }
        puts("");
    }
}

/*
1 1 
1
1 1
*/

By 皮了一下把班里电脑头像换成香蕉君很开心的 Cansult

一天连着翘两节那才叫爽!