edward_mj

[HDOJ3376 Matrix Again]最大费用最大流

【题目大意】

参见NOIP的传纸条。

【算法分析】

直接费用流~

对于时间复杂度分析一下：由于只增广两次，所以复杂度是O(2*SPFA)。

不需要担心点太多了~

【CODE】

#include #include #include const int N=721111;
const int E=2160111;
const int INF=1000000000;
struct gtp{int x,y,next,op,w,c;}g[E];
int n,e,S,T,cost;
int pos[622][622],ls[N],d[N],v[N],list[N],fa[N];

inline void addedge(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
    g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
    g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void init(){
    int i,j,tmp=0,w;
    e=0;
    for (i=1;i<=2*n*n+2;i++) ls[i]=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        pos[i][j]=++tmp;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++){
        scanf("%d",&w);
        addedge(pos[i][j],pos[i][j]+n*n,1,w);
        if (i        if (j      }
    S=n*n*2+1; T=S+1;
    addedge(S,1,2,0);
    addedge(n*n*2,T,2,0);
    addedge(1,n*n+1,1,0);
    addedge(n*n,n*n*2,1,0);
}

void spfa(){
    for (int i=1;i<=T;i++){
        d[i]=-INF;
        v[i]=0;
    }
    int head=0,tail=1,t;
    list[1]=S; v[S]=1; d[S]=0;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }
          }
        v[list[head]]=0;
    }
}

void change(){
    cost+=d[T];
    for (int i=T;i!=S;i=g[fa[i]].x){
      g[fa[i]].c–;
      g[g[fa[i]].op].c++;
    }
}

void work(){
    cost=0;
    spfa();
    change();
    spfa();
    change();
}

int main(){
    while (scanf("%d",&n)!=EOF){
        init();
        work();
        printf("%dn",cost);
    }
}

[HDOJ3373 Point]枚举+小优化 || 离散化+线段树+平衡树+二分答案

【题目大意】

定义点与点之间的距离为max(|Xi-Xj|,|Yi-Yj|)

给定N个点，将这N个点中每个点与最近点的距离加起来，输出SUM。

【算法分析】

算法1：

算了下复杂度O(N^2)的话加些优化应该可以卡过。

于是我把他们按x排序，x相等的按y排序。

然后枚举当前点i，并向前和向后枚举点j，如果出现abs(X[j]-X[i])>=now （其它now为当前答案），那么可以break退出循环。（最优化剪枝）

然后这样就可以9000MS左右AC了。

算法2：

同算法1那样排序。

再按X坐标离散化。

然后枚举当前点i，并二分答案（当前最短距离）。

问题转化为看是否存在点(X[j],Y[j])，使得abs(X[j]-X[i])<=ANS 且 abs(Y[j]-Y[i])<=ANS

于是就可以以X轴为线段树所划分的区间建立一棵线段树，线段树上再建立一棵以Y坐标为key值的平衡树。

然后在上面进行查找。每次查找的复杂度是O((lgN)^2)。

加上二分答案，每个点的处理复杂度为O((lgN)^3)。

所以总时间复杂度为O(N (lgN)^3 )。

空间复杂度为O(NlgN)。

因为最同一深度的线段树区间下，一个点只能出现在一个区间内。所以一个点最多出现lgN次。所以空间复杂度不是问题。

但是这个算法编程复杂度可能比较高。如果用STL的

【其它】由于我不会STL，所以算法2就不写了。。。

【CODE】

#include #include #include #include #include using namespace std;
const int N=101111;
const int INF=0x7FFFFFFF;
int n;
struct type{int x,y;}L[N];
long long ans;

inline bool cmp(type x,type y){
    if (x.x    if (x.x>y.x) return false;
    if (x.y    return false;
}

void input(){
    for (int i=1;i<=n;i++)
      scanf("%d%d",&L[i].x,&L[i].y);
    sort(&L[1],&L[n+1],cmp);
}

void work(){
    ans=0;
    int i,j,now;
    for (i=1;i<=n;i++){
        now=INF;

        j=i-1;
        while (j){
            if (L[i].x-L[j].x>=now) break;
            now            j–;
        }

        j=i+1;
        while (j<=n){
            if (L[j].x-L[i].x>=now) break;
            now            j++;
        }

        ans+=now;
    }
    cout << ans << endl;
}

int main(){
    while (scanf("%d",&n)!=EOF){
        input();
        work();
    }
}

[HDOJ3371 Connect the Cities]并差集、最小生成树、启发式合并

【题目大意】

有点已经成一个块了，让你加最少费用的边，使得它整个图成为一个连通块。

【算法分析】

经典最小生成树。

用并差集处理块，然后排序一下搞个kruskal。

但是很容易TLE。于是我加了那个启发式合并。

【其它】

尽管如此，我用G++交还是TLE,C++500多MS。

可能并差集写成非递归会好点。

【CODE】

#include #include #include #include #include #include using namespace std;
const int N=1000000;
int Tc,n,m,k,done,ans;
int f[N],d[N][3];
int num[N];

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

void input(){
    done=0; ans=0;
    int i,j,t,one,x;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        f[i]=i;
        num[i]=1;
    }
    for (i=1;i<=m;i++)
      scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
    for (i=1;i<=k;i++){
        scanf("%d%d",&t,&one);
        for (j=1;j          scanf("%d",&x);
          if (gf(x)!=gf(one)){
            if (num[f[x]]                num[f[one]]+=num[f[x]];
                f[f[x]]=f[one];
            }
            else{
                num[f[x]]+=num[f[one]];
                f[f[one]]=f[x];
            }
            done++;
          }
        }
    }
}

int cmp(const void *x,const void *y){
return ((int *)x)[2]-((int *)y)[2];
}

void work(){
    if (done==n-1) return;
    qsort(d[1],m,sizeof(int)*3,cmp);
    for (int i=1;i<=m;i++){
      int &x=d[i][0],&y=d[i][1];
      if (gf(x)!=gf(y)){
          if (num[f[x]]              num[f[y]]+=num[f[x]];
              f[f[x]]=f[y];
          }
          else{
              num[f[x]]+=num[f[y]];
              f[f[y]]=f[x];
          }

          done++;
          ans+=d[i][2];
          if (done==n-1) return;
      }
    }
}

void output(){
if (done==n-1) printf("%dn",ans);
else printf("-1n");
}

int main(){
    cin >> Tc;
    for (int i=1;i<=Tc;i++){
        input();
        work();
        output();
    }
}

[HDOJ3357 Stock Chase]维护传递闭包

【题目大意】

给出N个点，按读入顺序加入有向边，然后如果某条边加入以后，形成了环，那么就不加这条边。

问最后有多少条边不被加。

【算法分析】

维护一个闭包，如果加入边x->y，且y本来就可以到达x，那么这条边不加。

否则更新闭包。

复杂度O(MIN(n^4,T*n^2))。

【其它】

正解不知道是啥。。。这种方法明显水过，明天再问问人。。。

【CODE】

#include #include #include #include #include using namespace std;

int Tc=0,n,m,i,j,k,x,y,ans;
bool map[255][255];

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (;;){
        Tc++;
        scanf("%d%d",&n,&m);
        if (!n && !m) break;
        memset(map,false,sizeof(map));
        for (i=1;i<=n;i++) map[i][i]=true;
        for (ans=0,k=1;k<=m;k++){
            scanf("%d%d",&x,&y);
            if (map[y][x]) ans++;
            else if (!map[x][y]){
                map[x][y]=true;
                for (i=1;i<=n;i++)
                  for (j=1;j<=n;j++)
                    if (map[i][x] && map[y][j]) map[i][j]=true;
            }
        }
        printf("%d. %dn",Tc,ans);
    }
}

[HDOJ3359 Kind of a Blur]高斯消元、例题

【题目大意】

给定一个矩阵，A[i][j]=满足abs(i-ii)+abs(j-jj)<=d的T[ii][jj]的平均数。

让你还原成T[i,j]

【算法分析】

列方程，高斯消元。

【其它】

WA很多次，需要注意的是：消元时，那个rate必须是主元的那行做分母，否则有些情况下不行。。。

为什么会这样暂时不是很清楚，等下再YY一下。。。

【CODE】

#include #include #include #include #include using namespace std;

int m,n,d,cnt[122],pos[12][12];
double q[12][12],a[122][122],x[122];

bool input(){
scanf("%d%d%d",&n,&m,&d);
if (!n && !m && !d) return false;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%lf",&q[i][j]);
return true;
}

void init(){
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
memset(x,0,sizeof(x));
int i,j,ii,jj,tmp=1;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++,tmp++)
pos[i][j]=tmp;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
for (ii=1;ii<=m;ii++)
for (jj=1;jj<=n;jj++)
if (abs(ii-i)+abs(jj-j)<=d){
cnt[pos[i][j]]++;
a[pos[i][j]][pos[ii][jj]]=1.0;
}
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
a[pos[i][j]][m*n+1]=q[i][j]*cnt[pos[i][j]];
}

void guass(){
int i,j,k; double sum,rate;
for (k=1;k for (i=k,j=k;i<=n;i++) j=fabs(a[i][k])>fabs(a[j][k])?i:j;
for (i=k;i<=n+1;i++) swap(a[j][i],a[k][i]);
for (i=k+1;i<=n;i++)
for (rate=a[i][k]/a[k][k],j=k;j<=n+1;j++)
a[i][j]-=a[k][j]*rate;
/* if (a[i][k]!=0)
for (rate=a[k][k]/a[i][k],j=k;j<=n+1;j++)
a[i][j]=a[i][j]*rate-a[k][j];
这样写是错的！！！！！！！！！！！！
*/
}
for (i=n;i>=1;i–){
for (sum=0,j=i+1;j<=n;sum+=a[i][j]*x[j],j++);
x[i]=(a[i][n+1]-sum)/a[i][i];
}
}

void output(){
for (int i=1;i<=m;i++,printf("n"))
for (int j=1;j<=n;printf("%8.2lf",x[pos[i][j]]),j++);
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int Tc=0;
while (input()){
if (Tc) printf("n");
Tc++;
init();
n*=m;
guass();
n/=m;
output();
}
}