好题mark

1. 图论方法（最大权闭合子图）

#include <cstdio>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
 
const int N=1110;
const int E=5000;
const int oo=1000000000;
 
int node,src,dest,ne;
int head[N],work[N],Q[N],dist[N];
int pnt[E],nxt[E],flow[E];
int val[N][N],bonus[N][N],cost[N];
 
inline void init(int _node,int _src,int _dest)
{
    node=_node;
    src=http://www.mamicode.com/_src;>

2. DP方法（状态压缩）
#include<string.h>
#include<iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
//typedef long long LL;
typedef __int64 LL;
const int maxn=1<<11;
LL A[11][11],B[11],g[11][11],dp[12][maxn],w[12][maxn],ww[maxn][maxn],m,n;

LL Cal()
{
    LL i1,j1,k1,ii,kk,i,j,k,a[15];

    for(i=0;i<m;i++)
        for(j=0;j<1<<n;j++)
            dp[i][j]=-100000000;
    memset(w,0,sizeof(w));



    for(j=0;j<1<<n;j++)
    {
        i=j,ii=0,k=0;
        while(i)
        {
            if(i&1)
                a[ii++]=k;
            k++;
            i=i>>1;
        }
        for(kk=0;kk<m;kk++)
        {
            for(i=0;i<ii;i++)
                w[kk][j]+=A[a[i]][kk]-B[kk];
            for(i=0;i<ii;i++)
                for(k=i+1;k<ii;k++)
                    w[kk][j]+=g[a[i]][a[k]];
        }
    }//这里计算在ww景点，状态j游玩此景点的收益



    for(j=0;j<1<<n;j++)
        dp[0][j]=w[0][j];//初始化dp，



    for(i=0;i<1<<n;i++)
    {
        for(k=1,j=0;j<=i;j++)
            if((j|i)==i)
                ww[i][k++]=j;
        ww[i][0]=k;

    }//这里for循环做的是寻找如果状态i游玩了上一个景点，那么游玩下一个景点的状态可能有ww[i][0]个，分别是从ww[i][1]到ww[i][ww[i][0]]



    for(i1=1;i1<m;i1++)//在i1点，在i1-1点剩的人的二进制表示为k1
    {
        for(j1=0;j1<1<<n;j1++)
        {
            for(k1=1;k1<ww[j1][0];k1++)
            {
                ii=ww[j1][k1];
                if(dp[i1][ii]<dp[i1-1][j1]+w[i1][ii])
                    dp[i1][ii]=dp[i1-1][j1]+w[i1][ii];
            }
        }
    }//dp[i][j]表示状态j在i游玩，则总的最大收益是这个

    for(kk=0,i=0;i<1<<n;i++)
        if(dp[m-1][i]>kk) kk=dp[m-1][i];
    return kk;
}
void Init()
{
    LL i,j;
    for(i=0;i<m;i++)//每个人进所需的钱
        scanf("%I64d",&B[i]);
    for(i=0;i<n;i++)//i人到j地方的兴趣
        for(j=0;j<m;j++)
            scanf("%I64d",&A[i][j]);
    for(i=0;i<n;i++)//i与j同时进再加的兴趣
        for(j=0;j<n;j++)
            scanf("%I64d",&g[i][j]);
}

int main()
{
    LL ii;
    while(scanf("%I64d%I64d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        Init();
        ii=Cal();
        if(ii==0) printf("STAY HOME\n");
        else printf("%I64d\n",ii);
    }
    return 0;
}



HDU 4049