zoj3408 Gao
//这题Gao死我了！！！
题意：Gao这个函数可以用来算出有向图中从0到达某点的最短路径条数，用Gao算出0到所有点的最短路径条数了，现问有多少条路径经过点v。输出答案的后10位。
解析：首先，这题有10000个点50000条边，对每点求最短路径是不可能的。观察最短路径以后我们可以知道，一个点v在一条最短路径里最多出现1次，要么出现在路径的末尾，要么出现在路径的中间，对于出现在末尾的最短路径数我们定义为cnt1[v]，而我们在计算0点到所有点的最短路径过程中是可以记录cnt1[v]的：
if(dis[u]+w<dis[v]) //u->v权值为w
{
dis[v]=dis[u]+w;
cnt1[v]=cnt1[u];
tmp.v=v;tmp.dis=dis[v];
que.push(tmp);
}
else if(dis[u]+w==dis[v])
{ cnt1[v]+=cnt1[u];
cnt1[v]%=MOD;
}
至于v出现在最短路径的中间的情况，定义cnt2[v]表示最短路径中从v出发的路径条数，那么根据组合数学定义,v出现在最短路中间的最短路径条数=cnt1[v]*cnt2[v]。cnt2[v]可以用Calc(v)进行递归计算(貌似也可以叫树形DP,好像还可以拓扑排序以后之间DP），假如有t1,t2,t3...tn与v邻接且v->t1,v->t2,v->t3...,v->tn都在最短路径上，那么同样根据组合数学加法原理有cnt2[v]=cnt2[t1]+cnt2[t2]+...cnt[tn]。因为t1,t2,tn都在最短路径上，所以cnt2[v]+=n;
最终ans[v]=cnt1[v]+cnt1[v]*cnt2[v]。
这题比较阴险的地方在于答案要保留后10位，而进行乘法的过程中会超long long（事实证明，在计算cnt1的过程中也会超long long，在这地方无限WA T_T）要用到布斯(Booth)乘法：
long long Mul(long long lhs,long long rhs)
{
long long lhs2=lhs%100000;
long long rhs2=rhs%100000;
return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}
最后贴一个完整的代码：
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const long long MOD=10000000000LL;
struct Edge
{
int v,next,w;
}buf[50010];
struct Node
{
int v,dis;
};
const int INF=1<<30;
bool operator<(Node a,Node b)
{
return a.dis>b.dis;
}
int head[10010];
int dis[10010];
long long cnt[10010];
bool flag[10010];
int N,M,nE,Q;
void addEdge(int u,int v,int w)
{
buf[nE].v=v;buf[nE].w=w;buf[nE].next=head[u];head[u]=nE++;
}
long long Mul(long long lhs,long long rhs)
{
long long lhs2=lhs%100000;
long long rhs2=rhs%100000;
return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}
long long add(long long a,long long b)
{
a+=b;
if(a>=MOD)
a-=MOD;
return a;
}
void Dijkstra(int src)
{
Node tmp,cur;
tmp.v=src;tmp.dis=0;
for(int i=0;i<=N;i++)
dis[i]=INF;
dis[src]=0;
memset(flag,false,sizeof(flag));
memset(cnt,0,sizeof(cnt));
priority_queue<Node> que;
cnt[src]=1;
que.push(tmp);
while(!que.empty())
{
cur=que.top();que.pop();
int u=cur.v,d=cur.dis;
if(flag[u])continue;
flag[u]=true;
for(int i=head[u];i!=-1;i=buf[i].next)
{
int v=buf[i].v,w=buf[i].w;
if(d+w<dis[v])
{
dis[v]=d+w;
cnt[v]=cnt[u];
tmp.v=v;tmp.dis=dis[v];
que.push(tmp);
}
else if(d+w==dis[v])
{ cnt[v]+=cnt[u];
cnt[v]%=MOD;
}
}
}
}
long long rec[10010];
long long Gao(int s)
{
long long c=0;
if(rec[s]!=-1)return rec[s];
for(int i=head[s];i!=-1;i=buf[i].next)
{
int v=buf[i].v;
if(dis[s]+buf[i].w==dis[v]&&s!=v)
{
c++;
if(rec[v]==-1)
rec[v]=Gao(v);
c=add(c,rec[v]);
}
}
return c%MOD;
}
int main()
{
//freopen("data","r",stdin);
//freopen("mout","w",stdout);
while(scanf("%d%d%d",&N,&M,&Q)!=EOF)
{
memset(head,0xff,sizeof(head));
memset(rec,0xff,sizeof(rec));
nE=0;
while(M--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
Dijkstra(0);
int q;
while(Q--)
{
scanf("%d",&q);
if(cnt[q]<0)while(1);
long long ans=Mul(cnt[q],Gao(q)+1);
ans=ans%MOD;
printf("%010lld\n",ans);
}
//putchar(10);
}
return 0;
}POJ 3592 Instantaneous Transference
起初从boat大牛那里听说了这题，挺有意思的，就做了做。
题意：一辆坦克从N*M矩阵的左上角出发，每次往右或往 下走一格，每格可以是'#'(表示不可以走),'*'表示传送门，或者是数字，表示在该格可以获得的值（只能取一次），传送门可以传送到指定位置，你可以选择被传送或者走相邻的格，问坦克可以获得的值的和最大为多少。
解析：第一次看应该是个DP，（如果无传送门且可以走K轮，可以用网络流），但是矩阵中有传送门的存在，有可能形成环，所以要转化成DAG（有向无环图），可以以格子的相邻关系建边，然后求SCC，缩点再构图，边权为指向的格子的值，后求最长路（可以搜索，可以DP）。
WA了好几次，传送门有可能传到'#'的格子，格子是'#'的时候也要向相邻格子建边，题目求的是坦克可以获得的最大值，而不是到右下角的值（上回做了道类似的网络流，惯性导致想当然了）。
最后贴个代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct Edge
{
int v;
int next;
}buf[50000];
int head[2000],head2[2000],nE;
bool instack[2200];
int dfn[2020],low[2020],idx,Bcnt;
int stack[2020],top;
int Belong[2020];
int ores[2200];
int Bores[2200];
int N,M;
void addEdge(int u,int v)
{
buf[nE].v=v;buf[nE].next=head[u];head[u]=nE++;
}
void addEdge2(int u,int v)
{
buf[nE].v=v;buf[nE].next=head2[u];head2[u]=nE++;
}
void Tarjan(int cur)
{
dfn[cur]=low[cur]=++idx;
stack[top++]=cur;
instack[cur]=true;
for(int i=head[cur];i!=-1;i=buf[i].next)
{
int v=buf[i].v;
if(!dfn[v])
{
Tarjan(v);
if(low[cur]>low[v])
low[cur]=low[v];
}
else if(instack[v]&&low[cur]>dfn[v])
{
low[cur]=dfn[v];
}
}
if(dfn[cur]==low[cur])
{
Bcnt++;
Bores[Bcnt]=0;
int j;
do
{
j=stack[--top];
instack[j]=false;
Belong[j]=Bcnt;
Bores[Bcnt]+=ores[j];
}while(j!=cur);
}
}
void Rebuld()
{
memset(head2,0xff,sizeof(head2));
for(int i=0;i<N*M;i++)
for(int j=head[i];j!=-1;j=buf[j].next)
{
int v=buf[j].v;
if(Belong[i]!=Belong[v])
addEdge2(Belong[i],Belong[v]);
}
}
void go()
{
memset(dfn,0,sizeof(dfn));
memset(instack,false,sizeof(instack));
idx=Bcnt=top=0;
for(int i=0;i<N*M;i++)
if(!dfn[i])
Tarjan(i);
Rebuld();
int dis[2020];
memset(dis,0,sizeof(dis));
dis[Belong[0]]=Bores[Belong[0]];
queue<int> que;
que.push(Belong[0]);
bool inq[2020];
memset(inq,false,sizeof(inq));
inq[Belong[0]]=true;
while(!que.empty())
{
int cur=que.front();que.pop();
inq[cur]=false;
for(int i=head2[cur];i!=-1;i=buf[i].next)
{
int v=buf[i].v;
if(dis[v]<dis[cur]+Bores[v])
{
dis[v]=dis[cur]+Bores[v];
if(!inq[v])
{
inq[v]=true;
que.push(v);
}
}
}
}
int ans=-1;
for(int i=1;i<=Bcnt;i++)
if(dis[i]>ans)
ans=dis[i];
printf("%d\n",ans);
}
char map[45][45];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(head,0xff,sizeof(head));
nE=0;
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)
scanf("%s",map[i]);
memset(ores,0,sizeof(ores));
for(int i=0,r,c;i<N;i++)
for(int j=0;j<M;j++)
if(map[i][j]!='#')
{
if(i+1<N&&map[i+1][j]!='#')addEdge(i*M+j,(i+1)*M+j);
if(j+1<M&&map[i][j+1]!='#')addEdge(i*M+j,i*M+j+1);
ores[i*M+j]=map[i][j]-'0';
if(map[i][j]=='*')
{
ores[i*M+j]=0;
scanf("%d%d",&r,&c);
if(map[r][c]!='#')
addEdge(i*M+j,r*M+c);
}
}
go();
}
return 0;
}
0MS
差分约束专题
先摘抄一段：
如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径问题。观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。我们再增加一个源点s,s与所有定点相连，边权均为0。对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[ i]}即为一组可行解。
#include<iostream>
#include <cstdio>
using namespace std;
struct Edge
{
int u,v,w;
}e[101];
int sum[101];
int M,N;
bool BellmanFord()
{
for(int i=0;i<=N;i++)
sum[i]=0;
for(int k=0;k<N;k++)
for(int i=0;i<M;i++)
if(sum[e[i].u]+e[i].w<sum[e[i].v])
sum[e[i].v]=sum[e[i].u]+e[i].w;
for(int i=0;i<M;i++)
if(sum[e[i].u]+e[i].w<sum[e[i].v])
return false;
return true;
}
int main()
{
while(scanf("%d",&N),N)
{
scanf("%d",&M);
char op[3];
int si,ni,ki;
for(int i=0;i<M;i++)
{
scanf("%d%d%s%d",&si,∋,op,&ki);
if(op[0]=='g')
{
e[i].u=si+ni;
e[i].v=si-1;
e[i].w=-ki-1;
}
else
{
e[i].u=si-1;
e[i].v=si+ni;
e[i].w=ki-1;
}
}
if(!BellmanFord())
printf("successful conspiracy\n");
else
printf("lamentable kingdom\n");
}
return 0;
}
poj 3169 Layout难度*
题意：农夫FJ的牛排成一行等着吃饭，有些牛相互讨厌，他们之间距离的至少大于di，有些牛相互暧昧，他们之间的距离最多小于li问满足条件的队伍的最长距离。
解析：应该是比较水的一个题了(第一次做多校一个类似的题时居然没看出来)。求最大值，用最短路。如果A与B相互讨厌，他们之间的距离应大于di，则有dis[B]-dis[A]>=di，建一条<B,A,-di>的边。暧昧时同理。spfa求最短路时出现负环说明无解，dis[N]=INF则说明牛的位置可以是任意的(因为没有限制条件传递到N,所以N的值是初始的值，即N的位置不受限制),否则输出dis[N]。(其实应该添加dis[i]>=dis[i-1]的，但没加也过了)
poj 2983 Is the Information Reliable?难度**
题意：跟上面一题是一样的，这题有两种输入：P A B X表示A到B的距离正好等于X，V A B表示A的距离至少比B大1。问满足条件的解是否存在。
解析：对于P A B X，即dis[A]-dis[B]=X可以转化为：X<=dis[A]-dis[B]<=X ，据此构出两条边。对于V A B 即dis[A]-dis[B]>=1，再构造出边。这题要小心了，很多人用BellmanFord过用SPFA Wa了，要注意有些点是孤立点，或者一些集合构成孤立的集合，所以我们要建一个超级源点，连到所有的点，边的w=0 。最后判负环即可。
zoj 1455 Schedule Problem难度***
题意：一个工程分为N个部分，给出每个部分持续时间，以及几对部分之间的关系：FAS, FAF, SAF and SAS.输出每个部分的起始时间。
解析：约束关系比较明朗,以t[i]表示部分i什么时候开始d[i]表示部分i的持续时间，则有：
FAS: t[a]>=t[b]+d[a]
FAF: t[a]>=t[b]+d[b]-d[a]
SAS: t[a]>=t[b]
SAF: t[a]>=t[b]+d[b]
求最长路，设一个超级源点到所有点的权值为0.最后输出t[i]即可。
图的割点与割边学习笔记
割点
割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。
直观地说，就是删除了连通图的某点后，图不在连通，而是分为几个连通分量。
性质：（1）考虑根节点Root，如果Root有数量多于1的子结点时，Root是割点。
（2）考虑非根结点u，当且仅当u的某个儿子及儿子的子孙均没有指向u的祖先的后向边时，u是割点。（LOW[v]>=DFN[u],v是u的孩子）
代码：
void DFS(int cur,int par)
{
dfn[cur]=low[cur]=++Index;
int size=adj[cur].size();
int cnt=0;
for(int i=0;i<size;i++)
{
int v=adj[cur][i];
if(!dfn[v])
{
cnt++;
DFS(v,cur);
if(low[cur]>low[v])
low[cur]=low[v];
if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
flag[cur]=true;
}
else if(v!=par&&low[cur]>dfn[v])
low[cur]=dfn[v];
}
}
割边
割边：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。
性质: 对于一条边<u,v>，v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时，<u,v>是割边。（LOW[v]>DFN[u]）
代码：
void CutEdge(int cur,int par)
{ dfn[cur]=low[cur]=++Index;
for(int i=head[cur];i;i=buf[i].next)
{
int v=buf[i].v;
if(v==par)continue;
if(!dfn[v])
{
CutEdge(v,cur);
if(low[cur]>low[v])
low[cur]=low[v];
if(low[v]>dfn[cur])
{
ans[nAns++]=buf[i].id;
}
}
else if(low[cur]>dfn[v])
low[cur]=dfn[v];
}
}
相关习题：
POJ 1144 Network 赤果果的求割点的题。
相关链接:
Beyond the Void的讲解，很精彩
推荐阅读：
lrj的黑书P285
网络流题目记录
同之前的线段树题目记录一样，持续更新中，在此膜拜一下小HH。
hdu 3081 Marriage Match II
n男n女过家家，女生可以挑没有跟她吵过架的男生匹配，也可与没有跟她朋友吵过架的男生匹配（可以认为是她喜欢的男生）。每轮游戏，每个女生选个她没选过的男生，问游戏最多能进行几轮？
构图：先用并查集处理女生友情的传递。每个女向她喜欢的所有男生以及她朋友喜欢的男生连一条容量为1的边。二分最大能进行的轮数ans，源点向每个女生连一条容量为ans的边，每个男生向汇点连一条容量为ans的边。判断最大流是否等于ans*N;
hdu 3277 Marriage Match III
同上，每个女生可以跟最多K个她不喜欢的男生匹配。
构图：每个女生拆为两个点Gi1,Gi2。Gi1连一条容量为K的边到Gi2。每个Gi2连一条容量为1的边到女生i不喜欢的男生，源点连容量为ans的边到每个Gi1。其余同上。
一开始用Dinic，无限TLE~~~ T_T 。万般无奈下，只好上Qinz大牛的博客膜拜了ISAP的模板，再结合网上各路神牛的论文，终于得出了一份自己的ISAP模板～，提交果断AC～
hdu 3416 Marriage Match IV
有向图，求起点到终点的最短路的条数。
构图：求最短路，起点到所有点的最短路，所有边反向，求终点到所有点的最短路，对于边
poj 3498 March of the Penguins
有点类似2711，把柱子改成了冰块。而冰块上有一些企鹅，企鹅们要选一块冰块聚会,聚会点要求所有企鹅都能到达。给出企鹅的跳跃距离。找出所有的聚会点。
构图：基本同2711，这回要枚举点作为汇点。只要最大流等于除这冰块上的所有企鹅个数即可作为集结点，注意冰块是0起始的（调试到半夜一直出不了样例，原来。。。。）。
poj 3469 Dual Core CPU
网络流经典题目。最小割。一块CPU使用A模式要耗费Ai使用B模式耗费Bi，不同CPU交换数据耗费Wij，求a到b模式工作的最小耗费。
构图:题意比较囧，总之，源点连到所有CPU权值为使用Ai,CPU到汇点的权值为Bi。不同的CPU连Wij的边。求最大流，根据最大流最小割得解。
poj 1149 PIGS
农夫有M猪圈，有一天他要卖猪，但他没有猪圈钥匙而顾客有（好囧）。顾客来了以后打开他能打开的所有猪圈。买走一定数量的猪，然后关门。农夫可以在关门前把剩余的猪转移到别的猪圈。问农夫最多能卖多少猪。
构图：直接以猪圈和顾客为点，数量为边，TLE了。这题构图好难，这篇文章解释得很Nice~膜拜！