boat's Blog

swain[王雨舟](394528923) 22: wudiswain[王雨舟](394528923) 22:25:50
一张地图上，有一些矿点，每个矿点上都一个一定数量的矿（每个矿的量不一定相同） ，图上有些点可能是障碍物，现在坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开，问最多能有得到多少矿点，坦克开过矿点后矿点的矿全部给坦克
wudisplay[bsed刘通](357240143) 22:26:17
费用流？
wudiswain[王雨舟](394528923) 22:26:20
各位大牛，赶紧秒杀了这个。。
wudiswain[王雨舟](394528923) 22:26:34
。。费..
wudisplay[bsed刘通](357240143) 22:26:41
没描述啊
wudiswain[王雨舟](394528923) 22:26:51
坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开
wudisplay[bsed刘通](357240143) 22:27:06
DP就行了吧？
wudiswain[王雨舟](394528923) 22:27:11
恩
wudiswain[王雨舟](394528923) 22:27:15
这是问题一
wudiswain[王雨舟](394528923) 22:27:26
还有改进版的
wudiswain[王雨舟](394528923) 22:27:33
现在图上有一些传送门
wudisplay[bsed刘通](357240143) 22:27:32

wudiswain[王雨舟](394528923) 22:27:44
每个传送门指定到图上 的一个点
wudiswain[王雨舟](394528923) 22:27:54
现在问你最多能有多少矿
wudiswain[王雨舟](394528923) 22:28:14
各位观众赶紧来秒杀这个
wudisplay[bsed刘通](357240143) 22:28:21
擦，这不是你问过小红的嘛
wudiswain[王雨舟](394528923) 22:28:39
。。擦，我哈尔滨回来后今天花了一天才AC
wudisplay[bsed刘通](357240143) 22:28:58
这种题，给他们说有意义么...反正我不会
wudiwudiswain[王雨舟](394528923) 22:29:31
。。我只是想说，不搞ACM的话，类似这种东西是很难写的。。
wudisplay[bsed刘通](357240143) 22:29:36

wudiswain[王雨舟](394528923) 22:29:47
刘大牛。。你怎么可能不会
wudisplay[bsed刘通](357240143) 22:29:48
果然比我有远见
wudiswain[王雨舟](394528923) 22:30:25
我只是想让听众有点兴趣而已
wudiswain[王雨舟](394528923) 22:30:37
方帧去哪了

先将所有矿点缩点，然后求最长路

//boatswain 2010 /10/ 1
//*********************************
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N=25000;
int n,m,ans;
char map[50][50];
int loc[50][50];
int door[N];
int doornum;
int block[N];
int blocknum;
int ore[N];
int orenum;
//tarjan()
int scc,index,dfn[N],low[N],belong[N],num[N],sstack[N],top,out[N];
bool instack[N];
struct Edge{
	int v,next;
}edge[N];
int cnt;
int head[N];
int sum[N];
bool oyes(int i,int j){
	if (i>=0&&i<n&&j>=0&&j<m&&map[i][j]!='#')	return true;
	return false;
}
void addedge(int u,int v){
	edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}
struct Edge2{
	int v,next,val;
}e[N];
int aug;
int head2[N];
void addedge2(int u,int v,int val){
	e[aug].v=v;
	e[aug].val=val;
	e[aug].next=head2[u];
	head2[u]=aug++;
}
void init(){
	aug=cnt=doornum=blocknum=orenum=0;
	memset(head,-1,sizeof(head));
	memset(head2,-1,sizeof(head));
	memset(block,0,sizeof(block));
	memset(loc,0,sizeof(loc));
	memset(map,0,sizeof(map));
	memset(ore,0,sizeof(ore));
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++)  scanf("%s",map[i]);
	for (int i=0;i<n;i++)	
		for (int j=0;j<m;j++){
			loc[i][j]=i*m+j;
			if (map[i][j]=='*')		door[doornum++]=i*m+j;
			else if (map[i][j]=='#')	block[blocknum++]=i*m+j;
			else ore[loc[i][j]]=map[i][j]-'0';
		}
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++){
			if (!oyes(i,j)) continue;
			if (oyes(i+1,j)) addedge(loc[i][j],loc[i+1][j]);
			if (oyes(i,j+1)) addedge(loc[i][j],loc[i][j+1]);
		}
	for (int i=0;i<doornum;i++){
		int a,b;	scanf("%d%d",&a,&b);
		if (oyes(a,b)) addedge(door[i],loc[a][b]);
	}
}
int MAX(int a,int b){
    if (a<b) return b;
    return a;
}
int MIN(int a,int b){
    if(a<b)
        return a;
    return b;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++index;
    sstack[++top]=u;
    instack[u]=true;
    for (int j=head[u];j!=-1;j=edge[j].next){
        int v=edge[j].v;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=MIN(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u]=MIN(low[u],dfn[v]);
        }  
    }
    if(dfn[u]==low[u])
    {
        scc++;
        while(1)
        {
            int tmp=sstack[top--];
            instack[tmp]=0;
            belong[tmp]=scc;
            num[scc]++;
            if(tmp==u)
                break;
        }
    }
}
void SPFA(){
		bool vis[N];
		int dist[N],l,r,q[N*10],MAXQ=N+5;
		for (int i=0;i<scc+1;i++){
			dist[i]=-1;
			vis[i]=false;
		}
		l=r=0;
		q[r++]=0;
		dist[0]=0;
		while (l!=r){
			int u=q[l++];l%=MAXQ;
			vis[u]=false;
			for (int j=head2[u];j!=-1;j=e[j].next){
				int v=e[j].v;
				if (dist[v]<dist[u]+e[j].val){
					dist[v]=dist[u]+e[j].val;
				    if (!vis[v]){             
                       vis[v]=true; q[r++]=v;r%=MAXQ;
                       }
                }
		}
		}
		ans=0;
		for (int i=1;i<scc+1;i++){
            ans=MAX(ans,dist[i]);
            }
			
}
void solve(){
	scc=top=index=0;
	memset(dfn,0,sizeof(dfn));
	memset(sum,0,sizeof(sum));
	for (int i=0;i<n*m;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=0;i<n*m;i++)
		sum[belong[i]]+=ore[i];
	addedge2(0,belong[0],sum[belong[0]]);
	for (int i=0;i<n*m;i++){
		for (int j=head[i];j!=-1;j=edge[j].next){
			int v=edge[j].v;
			if (belong[i]!=belong[v])
				addedge2(belong[i],belong[v],sum[belong[v]]);
		}
	}
 SPFA();
}
void output(){
	printf("%d\n",ans);
}
int main(){
   // freopen("a.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		solve();
		output();
	}
	system("PAUSE");
}

 

Source Code

Problem: 3469		User: boatswain
Memory: 10900K		Time: 2922MS
Language: C++		Result: Accepted

• Source Code

  		#include <stdio.h>
  #include <iostream>
  #include <string.h>
  using namespace std;
  const int N=20010;
  int NN;
  const int MAXE=200010;
  const int inf=1<<30;
  int head[N];
  struct Edge
  {
          int v,next,w;
  }edge[MAXE*8];
  int cnt,n,m,s,t;
  void addedge(int u,int v,int w)
  {
          edge[cnt].v=v;
          edge[cnt].w=w;
          edge[cnt].next=head[u];
          head[u]=cnt++;
          edge[cnt].v=u;
          edge[cnt].w=0;
          edge[cnt].next=head[v];
          head[v]=cnt++;
  }
  int sap()
  {
          int pre[N],cur[N],dis[N],gap[N];
          int flow=0,aug=inf,u;
          bool flag;
          for(int i=0;i<=NN;i++)
          {
                  cur[i]=head[i];
                  gap[i]=dis[i]=0;
          }
          gap[s]=NN;
          u=pre[s]=s;
          while(dis[s]<NN)
          {
                  flag=0;
                  for(int &j=cur[u];j!=-1;j=edge[j].next)  
                  {
                          int v=edge[j].v;
                          if(edge[j].w>0&&dis[u]==dis[v]+1)
                          {
                                  flag=1;
                                  if(edge[j].w<aug) aug=edge[j].w;
                                  pre[v]=u;
                                  u=v;
                                  if(u==t)
                                  {
                                          flow+=aug;
                                          while(u!=s)
                                          {
                                              u=pre[u];
                                                  edge[cur[u]].w-=aug;
                                                  edge[cur[u]^1].w+=aug;
                                          }
                                          aug=inf;
                                  }
                  break;
                          }
                  }
                  if(flag)
                          continue;
                  int mindis=NN;
                  for(int j=head[u];j!=-1;j=edge[j].next)
                  {
                          int v=edge[j].v;
                          if(edge[j].w>0&&dis[v]<mindis)
              {
                    mindis=dis[v];
                    cur[u]=j;
              }
                  }
                  if((--gap[dis[u]])==0)
                          break;
                  gap[dis[u]=mindis+1]++;
                  u=pre[u];
          }
          return flow;
  }
  int main()
  {
          while(scanf("%d%d",&n,&m)!=EOF)
          {
                  s=0;t=n+1;cnt=0;
                  memset(head,-1,sizeof(head));
                  int a,b,c;
                  for(int i=1;i<=n;i++)
                  {
                          scanf("%d%d",&a,&b);
                          addedge(s,i,a);
                          addedge(i,t,b);
                  }
                  for(int i=1;i<=m;i++)
                  {
                          scanf("%d%d%d",&a,&b,&c);
                          addedge(a,b,c);
                          addedge(b,a,c);
                  }
                  int ans=0;
                 NN=n+2;
                  ans=sap();
                  printf("%d\n",ans);
          }
  }
  
  

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int N=210;
const int inf=0x7fffffff;
int match[N];
long long lack;
long long  w[N][N];
int n,m;
bool visx[N],visy[N];
long long lx[N],ly[N];
int wmax=300005;
bool dfs(int x)
{
     visx[x]=true;
     for(int y=1;y<=n;y++)
     {
       if(visy[y]) continue;
       int t=lx[x]+ly[y]-w[x][y];
       if(t==0)
       {
         visy[y]=true;
         if(match[y]==-1||dfs(match[y]))
         {
           match[y]=x;
           return true;
         }
       }
       else if(lack>t) lack=t;
     }
     return false;
}
void KM()
{
     memset(lx,0,sizeof(lx));
     memset(ly,0,sizeof(ly));
     memset(match,-1,sizeof(match));
     for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(w[i][j]>lx[i]) lx[i]=w[i][j];
     for(int x=1;x<=n;x++)
     {
       for(;;)
       {
        memset(visx,0,sizeof(visx));
        memset(visy,0,sizeof(visy));
        lack=inf;
        if(dfs(x)) break;
        for(int i=1;i<=n;i++)
        {
           if(visx[i]) lx[i]-=lack;
           if(visy[i]) ly[i]+=lack;
        }
       }
     }
}
int main()
{
    int t;
    long long sum;
    cin>>t;
    while(t--)
    {
      memset(w,0,sizeof(w));
      scanf("%d%d",&n,&m);
      for(int i=0;i<m;i++)
      {
       int a,b,c;
       cin>>a>>b>>c;
       if(wmax-c>w[a][b])
       w[a][b]=wmax-c;
       
      }
      KM();
      sum=0;
     for(int i=1;i<=n;i++)
     {
    // printf("match[%d][%d]=%d\n",match[i],i,inf-w[match[i]][i]);
     sum+=wmax-w[match[i]][i];
     }
     printf("%d\n",sum);
    }
}

#include <stdio.h>

#include <iostream>

#include <string.h>

using namespace std;

const int N=40000;

const int MAXE=20000000;

const int inf=1<<30;

int head[N],s,t,cnt,n,m,ans;

int d[N],pre[N];

bool vis[N];

int q[MAXE];

struct Edge

{

    int u,v,c,w,next;

}edge[MAXE];

void addedge(int u,int v,int w,int c)

{

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].c=c;

    edge[cnt].next=head[u];

    head[u]=cnt++;

    edge[cnt].v=u;

    edge[cnt].u=v;

    edge[cnt].w=-w;

    edge[cnt].c=0;

    edge[cnt].next=head[v];

    head[v]=cnt++;

}

int SPFA()

{

    int l,r;

    memset(pre,-1,sizeof(pre));

    memset(vis,0,sizeof(vis));

    for(int i=0;i<=t;i++) d[i]=inf;

    d[s]=0;

    l=0;r=0;

    q[r++]=s;

    vis[s]=1;

    while(l<r)

    {

        int u=q[l++];

        vis[u]=0;

        for(int j=head[u];j!=-1;j=edge[j].next)

        {

            int v=edge[j].v;

            if(edge[j].c>0&&d[u]+edge[j].w<d[v])

            {

                d[v]=d[u]+edge[j].w;

                pre[v]=j;

                if(!vis[v])

                {

                    vis[v]=1;

                    q[r++]=v;

                }

            }

        }

    }

    if(d[t]==inf)

        return 0;

    return 1;

}

void MCMF()

{

    int flow=0;

    while(SPFA())

    {

        ans+=d[t];

        int u=t;

        int mini=inf;

        while(u!=s)

        {

            if(edge[pre[u]].c<mini)

                mini=edge[pre[u]].c;

                u=edge[pre[u]].u;

        }

        flow+=mini;

        u=t;

        while(u!=s)

        {

            edge[pre[u]].c-=mini;

            edge[pre[u]^1].c+=mini;

            u=edge[pre[u]].u;

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        s=0;t=n+1;cnt=0;

        for(int i=0;i<=t;i++)

            head[i]=-1;

        for(int i=1;i<=m;i++)

        {

            int u,v,cost;

            scanf("%d%d%d",&u,&v,&cost);

            addedge(u,v,cost,1);

            addedge(v,u,cost,1);

        }

        addedge(0,1,0,2);

        addedge(n,t,0,2);

        ans=0;

        MCMF();

        printf("%d\n",ans);

    }

    return 0;

}