hdu1565 网络流或状态压缩DP-白红宇

hdu1565 网络流或状态压缩DP

阅读量：4679 次

发布时间：2019-06-09

本文共 1948 字，大约阅读时间需要 6 分钟。

对于网络流有一个定理：

最小点权覆盖集=最大网络流；

最大点权独立集=总权值-最小点权覆盖集；

网络流解法代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #define N 1010#define M 50010#define inf 1<<30using namespace std;struct Edge{    int to,val,next;}edge[M];int index[N],d[N],gap[N],e;void addedge(int from,int to,int val){    edge[e].to=to;    edge[e].val=val;    edge[e].next=index[from];    index[from]=e++;    edge[e].to=from;    edge[e].val=0;    edge[e].next=index[to];    index[to]=e++;}int source,des,n,m;//n is the number of pointint dfs(int pos,int flow){    if(pos==des)        return flow;    int i,j,v,val,lv,mind,c;    mind=n-1;//初始最小标号为n-1    lv=flow;    for(i=index[pos];i!=-1;i=edge[i].next)    {        v=edge[i].to;        val=edge[i].val;        if(val)        {            if(d[v]+1==d[pos])            {                c=min(lv,val);//对于该点的最小可行流                c=dfs(v,c);                edge[i].val-=c;//更新剩余图                edge[i^1].val+=c;                lv-=c;                if(d[source]>=n)return flow-lv;                if(lv==0) break;            }            if(d[v]
         
          1)                        addedge(pos(i,j),pos(i-1,j),inf);                    if(j>1)                        addedge(pos(i,j),pos(i,j-1),inf);                }                else                    addedge(pos(i,j),m*m+1,w);            }            n=m*m+2;        printf("%d\n",sum-sap(0,n-1));    }    return 0;}

状态压缩解法：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int s[1<<21];int map[22][22];int dp[2][1<<21];int main(){    int n,i,j,t,k,num=0;;    n=1<<21;    for(i=0;i<=n;i++)//记录可行状态        if((i&(i<<1))==0)            s[num++]=i;    while(scanf("%d",&n)!=EOF)    {        for(i=0;i
          
           (1<
           
            (1<