【BZOJ 1066】

每个格子有一定的限制，所以每个格子拆成两个点，然后限流即可。

UPD：垃圾题目，因为标号错误调了一天。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 10000000#define M(a) memset(a,0,sizeof a)#define F(i,j,k) for (int i=j;i<=k;++i)using namespace std;int list[51][51],num[51][51];int n,m,d,en=0;int S=0,T,sum=0,all=0;int u[100001],v[100001],h[100001],ne[100001],f[100001],map[100001];inline void add(int a,int b,int r){    u[en]=a;v[en]=b;ne[en]=h[a];f[en]=r;h[a]=en++;    u[en]=b;v[en]=a;ne[en]=h[b];f[en]=0;h[b]=en++;}inline bool tell(){    memset(map,-1,sizeof map);    queue 
          
            q; q.push(S); map[S]=0; while (!q.empty()){ int u=q.front(); q.pop(); for (int i=h[u];i!=-1;i=ne[i]){ if (map[v[i]]==-1&&f[i]){ map[v[i]]=map[u]+1; q.push(v[i]); } } } if (map[T]!=-1) return true; else return false;}inline int zeng (int k,int now)//进行增广路{ if (k==T) return now; int r=0; for (int i=h[k];i!=-1&&now>r;i=ne[i]){ if (map[k]+1==map[v[i]]&&f[i]!=0){ int t=zeng(v[i],min(now-r,f[i])); f[i]-=t;f[i^1]+=t;r+=t; } } if (!r) map[k]=-1; return r;}inline int dinic(){ int r=0,t; while (tell()) while (t=zeng(S,INF)) r+=t; return r; }inline bool ok(int a,int b,int c,int e){ if ((c-a)*(c-a)+(e-b)*(e-b)<=d*d) return true; return false;}int main(){ memset(h,-1,sizeof h); memset(ne,-1,sizeof ne); memset(u,-1,sizeof u); memset(v,-1,sizeof v); scanf("%d%d%d",&n,&m,&d); F(i,1,n)F(j,1,m) { char ch; cin>>ch; list[i][j]=ch-'0'; if (list[i][j]!=0){ num[i][j]=++sum; } } T=sum*2+1; F(i,1,n)F(j,1,m) { char ch; cin>>ch; if (ch=='L') { add(S,num[i][j]*2,1); all++; } } F(i,1,n)F(j,1,m) if ((i<=d||j<=d||i+d>n||j+d>m)&&(num[i][j])){ add(num[i][j]*2+1,T,INF); } F(i,1,n)F(j,1,m) if (num[i][j]) { add(num[i][j]*2,num[i][j]*2+1,list[i][j]); } F(i,1,n)F(j,1,m){ if (num[i][j]){ F(x,min(i-d,1),min(i+d,n)) F(y,min(j-d,1),min(j+d,m)) if (num[x][y]&&(i!=x||j!=y)) if (ok(i,j,x,y)) { add(num[i][j]*2+1,num[x][y]*2,INF); } } } cout<
           
            <
           
          
         
        
       
      
     

【BZOJ 1077】

最大权闭合子图的变形，增加了一个租用的方法。只需要在工作和机器之间加入一条流量为租用的边就可以最小割求解了。

UPD：垃圾题目，TLE了实在优化不过去了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define inf 0x3f3f3f3f#define ll long long#define maxm 400005#define maxn 10005 int h[maxm],to[maxm],fr[maxm],ne[maxm],fl[maxm],en=0,cur[maxn]; void add(int a,int b,int c){    to[en]=b;fr[en]=a;ne[en]=h[a];fl[en]=c;h[a]=en++;    to[en]=a;fr[en]=b;ne[en]=h[b];fl[en]=0;h[b]=en++;} int n,m,S=0,T=maxn-1,ans,dis[maxn];queue
          
           q;int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}bool tell(){ memset(dis,-1,sizeof dis); dis[S]=0;while (!q.empty()) q.pop(); q.push(S); while (!q.empty()) { int x=q.front();q.pop(); for (int i=h[x];i>=0;i=ne[i]) { if (dis[to[i]]==-1&&fl[i]>0) { dis[to[i]]=dis[x]+1; q.push(to[i]); } } } F(i,1,n+m) cur[i]=h[i]; cur[T]=h[T]; cur[S]=h[S]; if (dis[T]==-1) return false; return true;}int zeng(int k,int now){ if (k==T) return now; int r=0; for (int i=cur[k];i>=0&&now>r;i=ne[i]) { if (dis[to[i]]==dis[k]+1&&fl[i]>0){ int tmp=zeng(to[i],min(fl[i],now-r)); fl[i]-=tmp;fl[i^1]+=tmp;r+=tmp;// if (fl[i]) cur[k]=i; } } if (!r) dis[k]=-1; return r;}int main(){ memset(h,-1,sizeof h); n=read();m=read(); F(i,1,n) { int x,y,z; x=read(); add(S,i,x); ans+=x; x=read(); F(j,1,x) { y=read();z=read(); add(i,n+y,z); } } F(i,1,m) { int x; x=read(); add(n+i,T,x); } int tmp; while (tell()) while (tmp=zeng(S,inf)) ans-=tmp; printf("%d\n",ans);}
          
         
        
       
      
     

【BZOJ 1412】

水题，S连羊，T连狼，然后向四周连一条1的边，然后最小割即可。

UPD：人太懒，懒得写

【BZOJ 1433】

需要的和不需要的分在两边，认识的连一条边，然后最大匹配即可。（可以用网络流水过去）

还是太懒

【BZOJ 1475】

棋盘黑白染色，然后就是二分图了，相邻的不能取，就是最大点独立集的模型了。

懒

【BZOJ 1497】

最大权闭合子图裸题。直接1A

#include 
     
      #include 
      
       #include 
       
        #include 
        
          //#include 
         

q; memset(map,-1,sizeof map); map[S]=0; while (!q.empty()) q.pop(); q.push(S); while (!q.empty()) { int x=q.front(); q.pop();// cout<<"bfs"<

<

=0;i=ne[i]) {// cout<<"to "<

<

0) { map[to[i]]=map[x]+1; q.push(to[i]); } } }// cout<<"over"<

=0&&ret

0) { int tmp=zeng(to[i],min(fl[i],r-ret)); ret+=tmp; fl[i]-=tmp; fl[i^1]+=tmp; } if (!ret) map[k]=-1; return ret;} int n,m,x,a,b,c;ll ans=0; int main(){ memset(h,-1,sizeof h); Finout(); n=Getint(); m=Getint(); F(i,1,n) { x=Getint(); add(i+m,T,x); } F(i,1,m) { a=Getint(); b=Getint(); c=Getint(); add(S,i,c); add(i,m+a,inf); add(i,m+b,inf); ans+=c; }// cout<<"add over"<