usqwedf

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
    
const int Inf = 20150218 , N = 110;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
  
int n,m,A[N][N],T=0,i,j,k,x,y,Pr[N];
bool V[N];
 
bool Dfs(int x) {
    int i;
    Rep(i,1,n) if (!V[i]&&A[x][i]) { V[i]=1; if (!Pr[i]||Dfs(Pr[i])) { Pr[i]=x; return 1; } }
    return 0;
}
 
int main(){
    scanf("%d%d",&n,&m);
    Rep(i,1,m) { scanf("%d%d",&x,&y); A[x][y]=1; }
    Rep(i,1,n) Rep(j,1,n) Rep(k,1,n) A[i][j]|=(A[i][k]&A[k][j]);
    Rep(i,1,n) { memset(V,0,sizeof(V)); if (Dfs(i)) ++T; }
    printf("%d\n",n-T);
    return 0;
}

 

2015.2.19

 

Bzoj 1196  [HNOI2006]公路修建问题

答案具有单调性二分花费最多的公路的长度

Kruskal验证答案合法性

·一级公路条数是否符合要求

·并查集维护图的连通性（生成树）

#include <cstdio>
#include <algorithm>
  
using namespace std;
     
const int Inf = 20150219 , N = 20010;
  
#define Rep(i,x,y) for (i=x;i<=y;i++)
   
int n,R,Ans,K,m,F[N/2],L,x[N],y[N],C1[N],C2[N],i,j,Mid;
bool used[N];
 
int Find(int x) { return F[x]==x?x:F[x]=Find(F[x]); }
 
bool Ok(int C) {
    int i,k=0,p,q;
    Rep(i,1,n) F[i]=i;
    Rep(i,1,m) used[i]=0;
    Rep(i,1,m) 
       if (C1[i]<=C) { 
          p=Find(x[i]); q=Find(y[i]); 
           if (p!=q) F[p]=q,++k,used[i]=1;
        }
    if (k<K) return 0;
    Rep(i,1,m) {
        if (k==n-1) break;
        if (used[i]) continue;
        if (C2[i]<=C) {
            p=Find(x[i]); q=Find(y[i]); //其实C1连过 C2必然不会连
            if (p!=q) F[p]=q,++k;
        }
    }
    return k==n-1;
}
 
int main(){
    scanf("%d%d%d",&n,&K,&m);
    Rep(i,1,m-1) scanf("%d%d%d%d",&x[i],&y[i],&C1[i],&C2[i]);
    L=1; R=30001;
    while (L+1<R) { Mid=(L+R)>>1; if (Ok(Mid)) R=Mid,Ans=Mid; else L=Mid+1; }
    if (Ok(L)) Ans=L;
    printf("%d\n",Ans);
    return 0;
}

#include <cstdio>
#include <algorithm>
 
using namespace std;
    
const int Inf = 20150219 , N = 5110;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
  
int n,R,T,A[N+1][N+1],i,j,x,y,z;
 
int main(){
    scanf("%d%d",&n,&R);
    Rep(i,1,n) { scanf("%d%d%d",&x,&y,&z); ++x; ++y; A[x][y]+=z;  }
    Rep(i,1,N) Rep(j,1,N) A[i][j]+=A[i-1][j]+A[i][j-1]-A[i-1][j-1];
    Rep(i,R,N) Rep(j,R,N) T=max(T,A[i][j]-A[i-R][j]-A[i][j-R]+A[i-R][j-R]);
    printf("%d\n",T);
    return 0;
}

 

Bzoj 1197 [HNOI2006]花仙子的魔法

http://vfleaking.blog.163.com/blog/static/174807634201321193348312/

注意空间维度上的降维

F[i][1]=2 F[1][i]=2 * i

F[i][j]=F[i][j-1]+F[i-1][j-1]

#include <iostream>
#include <algorithm>
 
using namespace std;
    
const int Inf = 20150219 , N = 101;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
 
int n,m,i,j;
long long F[N][N];
 
int main(){
    cin>>m>>n;
    Rep(i,1,n) F[i][1]=2;
    Rep(i,1,m) F[1][i]=2 * i;
    Rep(i,2,n) Rep(j,2,m) F[i][j]=F[i][j-1]+F[i-1][j-1];
    cout<<F[n][m]<<endl;
    return 0;
}