T1

最优图像

【题目描述】
小E在好友小W的家中发现一幅神奇的图画，对此颇有兴趣。它可以被看做一个包含N×M个像素的黑白图像，为了方便起见，我们用0表示白色像素，1表示黑色像素。小E认为这幅图画暗藏玄机，因此他记录下了这幅图像中每行、每列的黑色像素数量，以回去慢慢研究其中的奥妙。
有一天，小W不慎将图画打湿，原本的图像已经很难分辨。他十分着急，于是找来小E，希望共同还原这幅图画。根据打湿后的图画，他们无法确定真正的图像，然而可以推测出每个像素原本是黑色像素的概率Pij%。那么，一个完整的图像的出现概率就可以定义为 ，其中Sij表示在还原后的图像中，像素是白色(0)还是黑色(1)。换句话说，一个完整图像出现概率就等于其所有黑色像素的出现概率之积。显然，图像的黑色像素不能包含概率为0的像素。
然而，小E对此也无能为力。因此他们找到了会编程的小F，也就是你，请你根据以上信息，告诉他们最有可能是原始图像的答案是什么。

【输入文件】
输入文件image.in的第一行是两个正整数N和M，表示图像大小。
接下来N行每行包含M个整数，表示每个像素是黑色像素的概率为Pij%。0 ≤ Pij < 100。
接下来一行有N个非负整数，表示每一行中黑色像素的个数。
接下来一行有M个非负整数，表示每一列中黑色像素的个数。

【输出文件】
输出文件image.out包含一个N×M的01矩阵，表示你还原出的图像。输出不包含空格。图像每行、每列中1的个数必须与输入一致，且是所有可能的图像中出现概率最大的一个。输入数据保证至少存在一个可能的图像。如果有多种最优图像，任意输出一种即可。

【样例输入】
2 2
90 10
20 80
1 1
1 1

【样例输出】
10
01

【样例解释】
共有两种可能的图像：
01
10
和
10
01
前者的出现概率是0.1×0.2=0.02，后者的出现概率是0.9×0.8=0.72，故后者是最优图像。

【数据规模和约定】
对于20%的数据，N , M ≤ 5
对于100%的数据，N , M ≤ 100

分析：
首先看到这道题，感觉又像贪心，又像dp

我们就应该有一种直觉：网络流

建图方式显而易见
但是每一种图的贡献是一种连乘的形式
而网络流好像只能计算相乘的形式，怎么办呢

中午吃饭的时候，dp表示：可以取一个lg，这样就可以把乘变加了
觉得非常有道理

建图：用1…n表示行，n+1…n+m表示列，

若Pij>0，则连一条边(i,n+j)，费用为-lg(Pij)*100000，容量为1

然后从s向1…n连边，费用为0，容量为这一行的黑色像素数量
然后从n+1..n+m向t连边，费用为0，容量为这一列的黑色像素数量
求这个图的最小费用最大流

写完测了一下，只能过掉20%的数据
听说需要用ZKW网络流优化
（本文中不再冗述，重点在于解题思路）

tip

注意输出的时候没有空格（mdzz，太不认真了。。。）

一定要用负费用跑最小费用最大流（可能是算法的本身bug）

要*100000转化成int类型，避免精度问题

对于网络流的模型，一定要有敏锐的直觉

#include
#include
#include
#include
#include

using namespace std;

const int INF=0x33333333;
const int N=102;
int n,m;
struct node{
    int x,y,v,c,nxt;
};
node way[N*N*2];
int s,t,h[N],z[N],C[N][N],st[N<<2],tot=-1,pre[N],dis[N<<2],a[N][N];
bool in[N];

void add(int u,int w,int z,int cc)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].c=cc;way[tot].nxt=st[u];st[u]=tot;
    tot++;
    way[tot].x=w;way[tot].y=u;way[tot].v=0;way[tot].c=-cc;way[tot].nxt=st[w];st[w]=tot;
}

int spfa(int s,int t)
{
    queue<int> Q;
    memset(dis,0x33,sizeof(dis));
    memset(in,0,sizeof(in));
    dis[s]=0; in[s]=1;
    Q.push(s);

    while (!Q.empty())
    {
        int now=Q.front(); Q.pop();
        for (int i=st[now];i!=-1;i=way[i].nxt)
            if (way[i].v&&dis[way[i].y]>dis[now]+way[i].c)
            {
                dis[way[i].y]=dis[now]+way[i].c;
                pre[way[i].y]=i;
                if (!in[way[i].y])
                {
                    in[way[i].y]=1;
                    Q.push(way[i].y);
                }
            }
        in[now]=0;
    }
    return dis[t]!=INF;
}

void solve()
{
    int ans=0;
    while (spfa(s,t))
    {
        int sum=INF;
        for (int i=t;i!=s;i=way[pre[i]].x)
            sum=min(sum,way[pre[i]].v);
        ans+=sum*dis[t];
        for (int i=t;i!=s;i=way[pre[i]].x)
            way[pre[i]].v-=sum,
            way[pre[i]^1].v+=sum;
    }
}

int get(int x)
{
    double xx=log(x);
    return (int)xx*100000;
}

void build()
{
    s=0; t=n+m+1;
    for (int i=1;i<=n;i++) add(s,i,h[i],0);
    for (int i=1;i<=m;i++) add(n+i,t,z[i],0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        if (C[i][j]!=0)
            add(i,j+n,1,-get(C[i][j]));     //负费用 
}

void print()
{
    for (int i=1;i<=n;i++)
        for (int j=st[i];j!=-1;j=way[j].nxt)
            if (way[j].y!=s&&way[j].v==0)
                a[way[j].x][way[j].y-n]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
            printf("%d",a[i][j]);
        printf("\n");
    }
}

int main()
{
    //freopen("image.in","r",stdin); 
    //freopen("image.out","w",stdout);
    memset(st,-1,sizeof(st));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++) scanf("%d",&C[i][j]);
    for (int i=1;i<=n;i++) scanf("%d",&h[i]);
    for (int i=1;i<=m;i++) scanf("%d",&z[i]);

    build();
    solve();
    print();    

    return 0;
}

T2

学校食堂

【题目描述】
小F的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。
由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or和and表示整数逐位或运算及逐位与运算，C语言中对应的运算符为”｜”和”＆”。
学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。
虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i个同学，最多允许紧跟他身后的Bi个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。
现在，小F想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完所有菜最少需要多少时间。

【输入文件】
输入文件dining.in的第一行包含一个正整数C，表示测试点的数据组数。
每组数据的第一行包含一个正整数N，表示同学数。
每组数据的第二行起共N行，每行包含两个用空格分隔的非负整数Ti和Bi，表示按队伍顺序从前往后的每个同学所需的菜的口味和这个同学的忍受度。
每组数据之间没有多余空行。

【输出文件】
输出文件dining.out包含C行，每行一个整数，表示对应数据中食堂完成所有菜所需的最少时间。

【样例输入】
2
5
5 2
4 1
12 0
3 3
2 2
2
5 0
4 0

【样例输出】
16
1

【样例说明】
对于第一组数据：
同学1允许同学2或同学3在他之前拿到菜；同学2允许同学3在他之前拿到菜；同学3比较小气，他必须比他后面的同学先拿菜……
一种最优的方案是按同学3，同学2，同学1，同学4，同学5做菜，每道菜所需的时间分别是0，8，1，6及1。

【数据规模和约定】
对于30%的数据，满足1 ≤ N ≤ 20。
对于100%的数据，满足1 ≤ N ≤ 1,000，0 ≤ Ti ≤ 1,000，0 ≤ Bi ≤ 7，1 ≤ C ≤ 5。
存在30%的数据，满足0 ≤ Bi ≤ 1。
存在65%的数据，满足0 ≤ Bi ≤ 5。
存在45%的数据，满足0 ≤ Ti ≤ 130。

分析：
（考试的时候写了一个超nb的暴力）

首先，看到B的范围，我们就应该有一种直觉：

状压dp

由题目可知，假如第i个人还没有取，则绝不可能取i+7之后的人，因为第i个人的最大容忍度不会超过7
如果第i个人之前全部取完了，则目前为止最后一个选的不可能是i-8之前的人，因为i-1不可能先于i-9及之前的人被选
故，可以设计状态f[i, S, k]表示到第i个人为止，之前的人都取过了，ta及ta后面7个人的还没取过的集合是S，前一个取的人是k的最优代价

S我们可以用二进制表示，k我们只需要记录一个对i的相对位置就行，数值从-8到7
（上一次选择的人只有可能在[i-8，i+7]这个区间内）

对于状态f[i, S, k]

• 如果S中没有第i个人了（第i个已经选过了），就将f [i, S, k]转移给f [i+1, S’, k-1]，这里S’多了第i+8个人
• 如果S中有第i个人，则枚举S中的一个符合要求的人j作为k之后所取的那个人，即将状态f [i, S, k]转移给f [i, S-{j}, j]，不要忘了加上花费

根据转移可以知道枚举时第一维必须从小到大枚举，第二维必须从大到小枚举

计算贡献的一点点优化：(a or b)-(a and b)=a xor b

tip

注意位运算的优先级

#include
#include
#include

using namespace std;

const int INF=0x33333333;
int n;
int T[1002],B[1002],f[1002][260][20];

int get(int x,int y)
{
    return x==0? 0:T[x]^T[y];
}

void dp()
{
    memset(f,0x33,sizeof(f));
    f[1][255][-1+10]=0;

    for (int i=1;i<=n;i++)
        for (int j=255;j>=0;j--)        //[i,i+7]未选状态 2^i 
            for (int kk=-8;kk<=7;kk++)
            {
                int k=kk+10;
                if (f[i][j][k]!=INF)
                {
                    if ((j&1)==0)         //没有i(实际上是一种不合法状态,我们把ta转移到合法状态)
                        f[i+1][(j>>1)+(1<<7)][k-1]=min(f[i+1][(j>>1)+(1<<7)][k-1],f[i][j][k]);
                    else
                    {
                        int mn=INF;
                        for (int l=0;l<=7;l++) if (j&(1<if (i+l>mn) break;
                            mn=min(mn,i+l+B[i+l]);
                            f[i][j-(1<10]=min(f[i][j-(1<10],f[i][j][k]+get(kk+i,i+l));
                        }
                    }
                }
            }
}

int main()
{
    //freopen("dining.in","r",stdin); 
    //freopen("dining.out","w",stdout);
    int C;
    scanf("%d",&C);
    while (C--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d%d",&T[i],&B[i]);
        dp();
        int ans=INF;
        for (int i=-8;i<=7;i++)
            ans=min(ans,f[n+1][255][i+10]);
        printf("%d\n",ans);
    }
    return 0;
}