最小AC爆零流

rp+=INF!(

noi,noip,高中信息学奥赛就算了,本来OIer就少(`_´)ゞ可算法,python,C++,C语言,计算机,Java太少人了吧,热度更是少的可怜,几乎都是0,lof还是拿来看同人好啊(´・ω・`)lof上写代码真是太鸡肋了还是blog好

集训day8t1 梦工厂

tql

tym983398371:









只写了60分的暴力,斜率优化还没来得及写,题解等我把100分的写了再补吧。。




60分


#include<iostream>


#include<algorithm>


#include<cstdio>


#include<cstring>


#include<vector>


#include<map>


using namespace std;


int n,m,a[100005],b[100005],f[100005];


long long cime;


inline 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;


}




void fan2()


{


int x;


int ans[15][15];


memset(ans,0,sizeof(ans)); 


for (int i=1;i<=n;i++) f[i]=read();


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


{


for (int j=1;j<=n;j++) a[j]=i*f[j];


for (int j=1;j<=10;j++)


{


for (int k=1;k<=n;k++) b[k]=j*f[k];


long long ans1=0;


for (int k=1;k<n;k++) 


{


ans1+=a[k+1]-b[k];


if (ans1>0) ans[i][j]+=ans1,ans1=0;


}


}


}


x=read();


int y;


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


{


y=x;


cime+=y*f[1];


x=read();


cime+=ans[y][x];


}


for (int i=1;i<=n;i++) cime+=f[i]*x;


printf("%lld\n",cime);


return ;


}




int main()


{


freopen("yume.in","r",stdin);


freopen("yume.out","w",stdout);


cime=0;


n=read();m=read();


if (n>1000) 


{


fan2();


return 0;


}


for (int i=1;i<=n;i++) scanf("%d",&f[i]);


int x;


x=read();


for (int i=1;i<=n;i++) a[i]=x*f[i];


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


{


cime+=a[1];


x=read();


for (int j=1;j<=n;j++) b[j]=x*f[j];


long long ans1=0,ans2=0;


for (int j=1;j<n;j++) 


{


ans1+=a[j+1]-b[j];


if (ans1>0) ans2+=ans1,ans1=0;


}


//for (int j=1;j<n-1;j++) ans2+=max(b[j]-a[j+1],)


cime+=ans2;


for (int j=1;j<=n;j++) a[j]=b[j];


}


for (int i=1;i<=n;i++) cime+=a[i];


printf("%lld\n",cime);


return 0;


}



点双连通分量和割顶和桥

ItalyLily:

对于无向图G,如果删除某个点u后,连通分量数目增加,称u为图的关节点(articulation vertex)或割顶(cut vertex)。对于联通图,割顶就是删除之后使图不再联通的点。


至于如何求割顶。


膜拜Tarjan大爷。


我们访问每一个点。在DFS森林中的边称为树边,第一次处理时从后代指向祖先的边称为反向边。然而在无向图中,除了树边,其他边都是反向边(有向图还有正向边和横叉边)。


对于无向图。我们讨论一个点是不是割顶,需要分两种情况:



  1. 这个点是DFS树的根节点,那么它是割顶,就需要它有两个或以上数目的儿子。

  2. 这个点不是DFS树的根节点,那么它没有【有可以到达它的祖先的反向边的子孙】。


所以就需要low值来判断(low值是它通过边或者它的子孙所能到达的节点的dfn值中中最小的dfn值)。


实际操作中,我们也是分两种情况讨论的:



  1. 它是根节点,那么就数一数它的儿子个数。

  2. 它不是根节点,如果它的low值不小于dfn值,并且它的父亲不是根节点,那么它的父亲就是割顶。(并不是直接判断它,而是通过儿子判断父亲。别问我为什么这样,我备用交换机抄的lrd的模板。)


然后我们就求出了割顶。


讨论我们这个题目[矿场搭建]:


求出所有的割顶之后,整个图被分成了几个联通块。我们对每个联通块含有的割顶数目进行讨论:



  1. 如果块里没有割顶,就建两个口,一个坏掉之后可以跑另一个。

  2. 如果块里只有一个割顶,那么就建一个口,这个口坏了就从割顶跑出去,割顶或者别的地方坏了就从这个口跑出去。

  3. 如果块里有两个或以上割顶,就一个也不建,如果一个点坏了就从割顶跑出去,一个割顶坏了就从别的割顶跑出去。


所以我们这时就有了两种办法:



  1. 求出割顶,然后对不是割顶的点进行dfs,能够求出一个块,然后统计这个块连接着多少割顶,如上讨论。

  2. 求割顶顺路求出BCC,然后对于每个BCC进行分类讨论(至于无向图的BCC,只要SCC的代码略加标记即可。http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076是一道BCC的模板题)。


P.S.


以下是来自CSDN的桥的相关知识:

桥    定义:

     在一张无向图中,如果去掉边(u,v)使得图的连通分支数增加,那么边(u,v)便称为桥.


  tarjan算法求无向图的桥:


     边(u,v)是无向图的桥当且仅当(u,v)满足 low[v]>DFN[u]


   简单说明:


     这个式子的言外之意也就是边(u,v)是v到达其祖先的必经之路,所以去掉边(u,v),连通分支数就会增加,但是如果u,v之间存在重边的话,就不是桥了,所以我们要对重边判定.