【SinGuLaRiTy-1041】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
计算树的直径
//方法：任选一个点作为起点进行一次BFS，找到最远点u。再以u为起点做一次BFS，找最长路即直径。 queue<int>point; void bfs(int a,int dis[]) { memset(dis,inf,sizeof dis); dis[a]=0; point.push(a); int v ,u ; while(!point.empty()) { u=point.front(); point.pop(); for(node *p=adj[u];p!=NULL;p=p->next) if(dis[(v=p->v)]>dis[u]+p->w) { dis[v]=dis[u]+p->w; point.push(v); } } } void solve()//输出直径长度 { bfs(1,dis); int flag=1; for(int i=2;i<=n;++i) if(dis[flag]<dis[i]) flag=i; bfs(flag,dis2); int flag2=1; for(int i=2;i<=n;++i) if(dis2[flag2]<dis2[i]) flag2=i; printf("%d",dis2[flag2]); }
LCA-返回a,b两点间的最短边权
返回a，b两点之间的最短边权 void dfs(int u) { int v ; for(node *p=adj[u];p!=NULL;p=p->next) { v=p->v; f[v][0]=u ; dep[v]=dep[u]+1 ; dfs(v); } } void init() { dep[root]=0 ; dfs(root); f[root][0]=root ; for(int j=1;j<MAXK;++j) for(int i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1]; } void adjust(int &u,int val) { for(int j=MAXK-1;j>=0;--j) if(dep[f[u][j]]>=val) u=f[u][j]; } int solve(int u,int v) { if(dep[u]>dep[v])adjust(u,dep[v]); else if(dep[u]<dep[v])adjust(v,dep[u]); if(u==v)return u; for(int j=MAXK-1;j>=0;--j) if(f[u][j]!=f[v][j]) u=f[u][j] ,v=f[v][j]; return f[u][0]; }
LCA 最近公共祖先-在线倍增
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int N=100001,L=20; int m,first[N],next[N],d[N],f[N][L]; inline void dfs(int x,int dep) { d[x]=dep; m=max(m,dep); for (int i=first[x];i;i=next[i]) dfs(i,dep+1); } int log2(int x) { int k=0; while (x>1) { x>>=1; k++; } return k; } int main() { int i,j,n,s,x,y,root; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&f[i][0]); if (!f[i][0]) root=i; next[i]=first[f[i][0]]; first[f[i][0]]=i; } dfs(root,0); s=log2(m); for (j=1;j<=s;j++) for (i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d",&n); while (n--) { scanf("%d%d",&x,&y); if (d[x]<d[y]) swap(x,y); s=log2(d[x]-d[y]); while (d[x]>d[y]) { if (d[x]-(1<<s)>=d[y]) x=f[x][s]; s--; } s=log2(d[x]); while (s>-1) { if (f[x][s]!=f[y][s]) { x=f[x][s]; y=f[y][s]; } s--; } printf("%d ",x==y?x:f[x][0]); } return 0; }
LCA 最近公共祖先-树链(双链树存图)
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #define N 100001 using namespace std; int a[N*2],d[N],down[N],next[N],top,f[2*N][18],loc[2*N][18],n,b[N]; int log2(int x) { int k=0; while (x>1) { x/=2; k++; } return k; } void dfs(int x,int dep) { int i; d[x]=dep; a[++top]=x; for (i=down[x];i!=0;i=next[i]) { dfs(i,dep+1); a[++top]=x; } } void init() { int i,j,s,x,k; for (i=1;i<=top;i++) { f[i][0]=d[a[i]]; loc[i][0]=a[i]; } s=log2(top); for (j=1;j<=s;j++) { k=top-(1<<j)+1; for (i=1;i<=k;i++) { x=i+(1<<(j-1)); if (f[i][j-1]<=f[x][j-1]) { f[i][j]=f[i][j-1]; loc[i][j]=loc[i][j-1]; } else { f[i][j]=f[x][j-1]; loc[i][j]=loc[x][j-1]; } } } } int main() { int i,k,x,y,t; scanf("%d",&n); for (i=1;i<=n;i++) down[i]=d[i]=next[i]=0; for (i=1;i<=n;i++) { scanf("%d",&x); next[i]=down[x]; down[x]=i; } top=0; dfs(down[0],1); for (i=1;i<=top;i++) if (b[a[i]]==0) b[a[i]]=i; init(); scanf("%d",&t); while (t>0) { t--; scanf("%d%d",&x,&y); x=b[x]; y=b[y]; if (x>y) swap(x,y); i=log2(y-x); k=y-(1<<i)+1; printf("%d ",f[x][i]<f[k][i]?loc[x][i]:loc[k][i]); } return 0; }
LCA 最近公共祖先-tarjan算法
void tarjan(int u) { for(node *p=adj[u];p!=NULL;p=p->next) { tarjan(p->v); Union(p->v,u); } vis[u]=1; for(int i=1;i<=ask[u][0];++i) if(vis[ask[u][i]]==1) printf("%d ",getroot(ask[u][i])); } void init() { scanf("%d",&m); while(m--) { scanf("%d%d",&a,&b); ask[a][++ask[a][0]]=b; ask[b][++ask[b][0]]=a; } for(int i=1;i<=n;++i) if(!in[i]) { tarjan(i); break; } }
前向星存图
struct node
{
int v ,w ;
node *next ;
}edge[MAXM<<1] ,*adj[MAXN] ,*code=edge ;
void add(int a,int b,int c)
{
++code;
code->v=b ,code->w=c ,code->next=adj[a] ;
adj[a]=code ;
}
最短路-Dijkstra
#define inf 0x3f3f3f3f
int dis[MAXN+5] ;
bool flag[MAXN+5] ;
void dijkstra(int a)
{
memset(dis,inf,sizeof dis);
dis[a]=0;
int minv ;
for(int i=1;i<=n;++i)
{
minv=0 ;
for(int i=1;i<=n;++i)
if(!flag[i]&&dis[minv]>dis[i])
minv=i;
if(minv==0)break;
flag[minv]=1;
for(node *p=adj[minv];p!=NULL;p=p->next)
dis[p->v]=min(dis[p->v],dis[minv]+p->w);
}
}
最短路-优先队列(堆优化的Dijkstra)
struct node
{
int v ,w ;
node *next ;
bool operator < (const node &a) const
{
return w>a.w;
}
}edge[MAXM<<1] ,*adj[MAXN] ,*code=edge ;
priority_queue<node, vector<node> > q;//注意必须开结构体，因为若在队列中一个元素的dis发生改变，队列不会对它重新排序
void dijkstra(int a)
{
memset(vis,0,sizeof vis);
memset(dis,inf,sizeof dis);
dis[a]=0 ;
q.push((node){a,0});
int u ,d ,v ;
while(!q.empty())
{
u=q.top().v ,d=q.top().w ;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(node *p=adj[u];p!=NULL;p=p->next)
if(!vis[(v=p->v)]&&dis[v]>dis[u]+p->w)
{
dis[v]=dis[u]+p->w;
q.push((node){v,dis[v]});
}
}
}
最短路-SPFA+判断负权环路
#define inf 0x3f3f3f3f
queue<int>point;
int dis[MAXN+5] ,vis[MAXN+5] ;
bool in[MAXN+5] ;
void spfa(int a)
{
int u ,v ;
memset(dis,inf,sizeof dis);
point.push(a);
dis[a]=0 ,in[a]=vis[a]=1 ;
while(!point.empty())
{
u=point.front();
in[u]=0 ;
point.pop();
for(node *p=adj[u];p!=NULL;p=p->next)
if(dis[(v=p->v)]>dis[u]+p->w)
{
dis[v]=dis[u]+p->w;
if(!in[v])
{
in[v]=1;
point.push(v);
if(++vis[v]>n)
{
puts("No Solution");
return;
}
}
}
}
}
最短路-Floyd
int dis[MAXN+5][MAXN+5] ;
void floyd()
{
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
if(k!=i)
for(int j=1;j<=n;++j)
if(i!=j&&k!=j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
一笔画问题-欧拉回路
#include <iostream>
#include <cstdio>
#define MAXN 105
using namespace std;
int n ,m ,a ,b ,map[MAXN+5][MAXN+5] ,temp[MAXN<<1] ,du[MAXN] ,cnt ;
int flag[5] ,pos ;
void dfs(int u)
{
for(int v=1;v<=n;++v)
if(map[u][v])
{
map[u][v]=map[v][u]=0;
dfs(v);
}
temp[++cnt]=u ;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&map[i][j]);
if(map[i][j])++du[i];
}
for(int i=1;i<=n;++i)
if(du[i]&1)
flag[++pos]=i ;
if(pos!=0&&pos!=2)
{
puts("No Solution!");
return 0;
}
if(pos==0)flag[1]=flag[2]=1;
dfs(flag[1]);
for(int i=cnt;i>1;--i)
printf("%d ",temp[i]);
printf("%d
",temp[1]);
return 0;
}
多叉树(森林)转二叉树
//输入N,M表示节点数和边数，再输入M组边关系，从1到N输出每个结点的父亲，根节点父亲为0 #include<cstdio> #include<algorithm> using namespace std; void read(int &x) { int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } #define MAXN 100 struct node { int l,r,f; }tree[MAXN+5]; int N,M; int root[MAXN+5],rs; bool d[MAXN+5][MAXN+5]; void rtb()//处理森林 { for(int i=1;i<=N;i++) if(!tree[i].f) root[++rs]=i; for(int i=rs;i>1;i--) { tree[root[i-1]].r=root[i]; tree[root[i]].f=root[i-1]; } } int main() { read(N),read(M); for(int i=1;i<=M;i++) { int x,y; read(x),read(y); d[x][y]=1;//先保存起来 } for(int i=1;i<=N;i++)//再处理 for(int j=1;j<=N;j++) if(d[i][j]) { if(tree[i].l==0) { tree[i].l=j; tree[j].f=i; } else { int t=tree[i].l; while(tree[t].r) t=tree[t].r; tree[t].r=j; tree[j].f=t; } } rtb(); for(int i=1;i<=N;i++) { if(i<N) printf("%d ",tree[i].f); else printf("%d",tree[i].f); } }
树的先序,中序,后序遍历-非递归版
//先序遍历 void PreOrder(Node* root) { assert(NULL != root) stack<Node*> store; store.push(root); // 根结点入栈 while(!store.empty()) { root = store.top(); // 在循环中，root记录的是当前准备输出的结点 store.pop(); cout << root->value << " "; // 输出当前结点 if(root->right_child) // 右孩子入栈 store.push(root->right_child); if(root->left_child) // 左孩子入栈 store.push(root->left_child); } } //中序遍历 void InOrder(Node* root) { assert(NULL != root); stack<Node*> store; while(root && !store.empty()) { if(root != NULL) { // 只要不为空，就一路向左结点方向走去 store.push(root); root = root->left_child; } else { // store.top()的左边都走过了 cout << store.top()->value << " "; // 输出当前结点 root = store.top()->right_child; store.pop(); } } } //后序遍历 void PostOrder(Node* root) { assert(NULL != root); Node* Pre = NULL; stack<Node*> store; while(root && !store.empty()) { if(root != NULL) { // 一路向左 store.push(root); root = root->left_child; } else { // stack.top()的左子树都输出完了 if(store.top()->right_child!=NULL && store.top()->right_child!=Pre) { // 右子树存在且没有输出过 root = root->right_child; } else { // 左右子树都输出过了 cout << store.top()->value << " "; Pre = store.top(); store.pop(); } } } }
树的先序,中序,后序遍历-递归版
//先序遍历 void preOrder1(BinTree *root) { if(root!=NULL) { cout<<root->data<<" "; preOrder1(root->lchild); preOrder1(root->rchild); } } //中序遍历 void inOrder1(BinTree *root) { if(root!=NULL) { inOrder1(root->lchild); cout<<root->data<<" "; inOrder1(root->rchild); } } //后序遍历 void postOrder1(BinTree *root) { if(root!=NULL) { postOrder1(root->lchild); postOrder1(root->rchild); cout<<root->data<<" "; } }
求树的重心
//以 POJ 1655 为例 //题意:给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的. #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N = 20005; const int INF = 1<<30; int head[N]; int son[N]; bool vis[N]; int cnt,n; int ans,size; struct Edge { int to; int next; }; Edge edge[2*N]; void Init() { cnt = 0; size = INF; memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); } void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void dfs(int cur) { vis[cur] = 1; son[cur] = 0; int tmp = 0; for(int i=head[cur];~i;i=edge[i].next) { int u = edge[i].to; if(!vis[u]) { dfs(u); son[cur] += son[u] + 1; tmp = max(tmp,son[u] + 1); } } tmp = max(tmp,n-son[cur]-1); if(tmp < size || tmp == size && cur < ans) { ans = cur; size = tmp; } } int main() { int T; scanf("%d",&T); while(T--) { Init(); scanf("%d",&n); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1); printf("%d %d ",ans,size); } return 0; }
最小生成树-Kruskal
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1010, MAXM = 100010;
int N, M;
struct Edge {
int a, b, d;
bool operator < (const Edge&t) const {
return d < t.d;
}
} ed[MAXM];
int tfa[MAXN];
void init() {
for (int i = 1; i<=N; ++i)
tfa[i] = i;
}
int root(int x) {
if (x == tfa[x]) return x;
return tfa[x] = root(tfa[x]);
}
void unite(int x, int y) {
tfa[root(x)] = root(y);
}
int Kruskal()
{
sort(ed+1, ed+M+1);
int i, cnt = 0, a, b, ans = 0;
for (i = 1; i<=M && cnt<M-1; ++i) {
a = ed[i].a;
b = ed[i].b;
if (root(a) != root(b))
unite(a, b), cnt++, ans += ed[i].d;
}
return ans;
}
int main()
{
init();
printf("%d", Kruskal());
return 0;
}
最小生成树-Prim
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 5010, MAXM = 500010;
const int INF = 0x3f3f3f3f;
int N, M;
struct Node {
int to, d;
Node *next;
}Edge[MAXM*2], *ecnt=Edge, *adj[MAXN];
void addedge(int a, int b, int c)
{
(++ecnt)->to = b;
ecnt->d = c;
ecnt->next = adj[a];
adj[a] = ecnt;
}
bool vis[MAXN];
struct Near {
int to, d;
Near(){}
Near(int a,int b){to=a;d=b;}
bool operator < (const Near&t) const {
return d > t.d;
}
};
int prim()
{
int cnt = 0, ans = 0;
priority_queue<Near> Q;
Q.push(Near(1, 0));
while (cnt < N && !Q.empty())
{
int u = Q.top().to, d = Q.top().d;
Q.pop();
if (vis[u]) continue;
ans += d;
vis[u] = 1;
++cnt;
for (Node*p = adj[u]; p; p=p->next)
if (!vis[p->to])
Q.push(Near(p->to, p->d));
}
return ans;
}
int main()
{
return 0;
}
拓扑排序-Toposort
int ans[MAXN+5] ;
bool vis[MAXN+5] ;
void topo()
{
int flag ;
for(int i=1;i<=n;++i)
{
flag=0;
for(int j=1;j<=n;++j)
if(!vis[j]&&!in[j])
{flag=j;break;}
if(!flag)
{
puts("no solution");
return;
}
ans[i]=flag ,vis[flag]=1 ;
for(node *p=adj[flag];p!=NULL;p=p->next)
--in[p->v];
}
for(int i=1;i<n;++i)
printf("%d ",ans[i]);
printf("%d
",ans[n]);
}
求割点
int low[MAXN] ,dfn[MAXN] ,cnt ,root_son ;
bool cutp[MAXN] ;
void dfs(int u,int fa)
{
int v ;
low[u]=dfn[u]=++cnt ;
for(node *p=adj[u];p!=NULL;p=p->next)
{
v=p->v;
if(!dfn[v])
{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])//在这里注意打上{}
{
if(fa!=-1)cutp[u]=1 ;
else ++root_son;
}
}
else if(v!=fa)
low[u]=min(low[u],dfn[v]);
}
}
void tarjon()
{
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
cnt=0;
for(int i=1;i<=n;++i)
if(!dfn[i])
{
root_son=0 ;
dfs(i,-1);
cutp[i]=root_son-1 ;
}
}
求割边(即桥)
int low[MAXN] ,dfn[MAXN] ,cnt ,root_son ;
int cnte[MAXM][2] ,pos ;
void dfs(int u,int fa)
{
int v ;
low[u]=dfn[u]=++cnt ;
for(node *p=adj[u];p!=NULL;p=p->next)
{
v=p->v;
if(!dfn[v])
{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
cnte[++pos][0]=u ,cnte[pos][1]=v ;
}
else if(v!=fa)
low[u]=min(low[u],dfn[v]);
}
}
void tarjon()
{
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
cnt=0;
for(int i=1;i<=n;++i)
if(!dfn[i])
dfs(i,-1);
}
双联通分量
stack< pair<int,int> >e;
pair<int,int>tmp ;
int dfn[MAXN] ,low[MAXN] ,cnt ,pos ;
void dfs(int u,int fa)
{
low[u]=dfn[u]=++cnt ;
int v ;
for(node *p=adj[u];p!=NULL;p=p->next)
{
v=p->v;
if(!dfn[v])
{
e.push(make_pair(u,v));
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
printf("Block No. %d
",++pos);
do
{
tmp=e.top();
e.pop();
printf("%d, %d
",tmp.first,tmp.second);
}while(tmp.first!=u||tmp.second!=v);
}
}
else if(v!=fa)
{
low[u]=min(low[u],dfn[v]);
if(dfn[u]>low[v])
e.push(make_pair(u,v));
}
}
}
void tarjon()
{
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
cnt=0;
for(int i=1;i<=n;++i)
if(!dfn[i])
dfs(i,-1);
}
有向图强连通分量
int cnt ,pos ,low[MAXN+5] ,dfn[MAXN+5] ,block[MAXN+5] ;
void dfs(int u)
{
int v ;
low[u]=dfn[u]=++cnt;
in[u]=1 ;
stack[++tail]=u;
for(node *p=adj[u];p!=NULL;p=p->next)
{
v=p->v;
if(!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(in[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++pos;
do
{
block[stack[tail]]=pos;
in[stack[tail]]=0;//忘记删除标记- -
--tail;
}while(stack[tail+1]!=u);
}
}
void tarjon()
{
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
cnt=pos=0;
for(int i=1;i<=n;++i)
if(!dfn[i])
dfs(i);
}
二分图判定-DFS
//以 HDU 2444 为例 //题意：给出一个无向图，若为二分图则求最大匹配，否则输出"No"。 #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N = 2005; int head[N],link[N]; bool vis[N],col[N]; int cnt,n,m; struct Edge { int to; int next; }; Edge edge[N*N]; void Init() { cnt = 0; memset(head,-1,sizeof(head)); memset(col,0,sizeof(col)); } void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } bool Color(int u) { for(int i=head[u]; ~i; i=edge[i].next) { int v = edge[i].to; if(!col[v]) { col[v] = !col[u]; if(!Color(v)) return false; } else if(col[v] == col[u]) return false; } return true; } bool dfs(int u) { for(int i=head[u]; ~i; i=edge[i].next) { int v = edge[i].to; if(!vis[v]) { vis[v] = 1; if(link[v] == -1 || dfs(link[v])) { link[v] = u; return true; } } } return false; } int match() { int ans = 0; memset(link,-1,sizeof(link)); for(int i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } return ans; } int main() { while(~scanf("%d%d",&n,&m)) { if(n == 1) { puts("No"); continue; } Init(); while(m--) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } col[1] = 1; if(!Color(1)) { puts("No"); continue; } printf("%d ",match()>>1); } return 0; }
二分图最大匹配-匈牙利算法
bool dfs(int u)
{
for(int v=1;v<=cntx;++v)
if(!vis[v]&&map[u][v])
{
vis[v]=1;
if(!cy[v]||dis(cy[v]))
{
cx[u]=v ,cy[v]=u ;
return 1;
}
}
return 0;
}
int match()
{
memset(cx,0,sizeof cx);
memset(cy,0,sizeof cy);
int ans=0;
for(int i=1;i<=cntx;++i)
if(!cx[i])
{
memset(vis,0,sizeof vis);
ans+=dfs(i);
}
return ans;
}
二分图最佳匹配-KM算法
const int inf=1e9,maxn=510; int KM(int m,int n,int tu[][maxn],int *match1,int *match2) { int s[maxn],t[maxn],l1[maxn],l2[maxn],p,q,ret=0,i,j,k; ///l1为左边的匹配分量，l2是右边的匹配分量 for(i=0; i<m; i++) { for(l1[i]=-inf,j=0; j<n; j++) l1[i]=tu[i][j]>l1[i]?tu[i][j]:l1[i]; if(l1[i]==-inf) return -1; } for(i=0; i<n; l2[i++]=0); memset(match1,-1,sizeof(int)*n); memset(match2,-1,sizeof(int)*n); for(i=0; i<m; i++) { memset(t,-1,sizeof(int)*n); for(s[p=q=0]=i; p<=q&&match1[i]<0; p++) { for(k=s[p],j=0; j<n&&match1[i]<0; j++) if(l1[k]+l2[j]==tu[k][j]&&t[j]<0) { s[++q]=match2[j],t[j]=k; if(s[q]<0) for(p=j; p>=0; j=p) match2[j]=k=t[j],p=match1[k],match1[k]=j; } } if(match1[i]<0) { for(i--,p=inf,k=0; k<=q; k++) for(j=0; j<n; j++) if(t[j]<0&&l1[s[k]]+l2[j]-tu[s[k]][j]<p) p=l1[s[k]]+l2[j]-tu[s[k]][j]; for(j=0; j<n; l2[j]+=t[j]<0?0:p,j++); for(k=0; k<=q; l1[s[k++]]-=p); } } for(i=0; i<m; i++) ret+=tu[i][match1[i]]; return ret; }
网络流-SAP
//以HDU 3549为例 #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef struct {int v,next,val;} edge; const int MAXN=20010; const int MAXM=500010; edge e[MAXM]; int p[MAXN],eid; inline void init(){memset(p,-1,sizeof(p));eid=0;} //有向 inline void insert1(int from,int to,int val) { e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; swap(from,to); e[eid].v=to; e[eid].val=0; e[eid].next=p[from]; p[from]=eid++; } //无向 inline void insert2(int from,int to,int val) { e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; swap(from,to); e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; } int n,m;//n为点数 m为边数 int h[MAXN]; int gap[MAXN]; int source,sink; inline int dfs(int pos,int cost) { if (pos==sink) { return cost; } int j,minh=n-1,lv=cost,d; for (j=p[pos];j!=-1;j=e[j].next) { int v=e[j].v,val=e[j].val; if(val>0) { if (h[v]+1==h[pos]) { if (lv<e[j].val) d=lv; else d=e[j].val; d=dfs(v,d); e[j].val-=d; e[j^1].val+=d; lv-=d; if (h[source]>=n) return cost-lv; if (lv==0) break; } if (h[v]<minh) minh=h[v]; } } if (lv==cost) { --gap[h[pos]]; if (gap[h[pos]]==0) h[source]=n; h[pos]=minh+1; ++gap[h[pos]]; } return cost-lv; } int sap(int st,int ed) { source=st; sink=ed; int ret=0; memset(gap,0,sizeof(gap)); memset(h,0,sizeof(h)); gap[st]=n; while (h[st]<n) { ret+=dfs(st,INT_MAX); } return ret; } int main() { int t,add=1; scanf("%d",&t); while(t--) { printf("Case %d: ",add++); scanf("%d%d",&n,&m); init(); int i; int ll,rr,cap; for(i=0;i<m;i++) { scanf("%d%d%d",&ll,&rr,&cap); insert1(ll,rr,cap); } printf("%d ",sap(1,n)); } return 0; }
最大流-ISAP
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define Min(a,b) ((a)<(b)?(a):(b))
#define clear(a) memset(a,0,sizeof a)
const int MAXN = 1010, MAXM = 10010;
const int INF = 1<<29;
struct Node {
int to, c;
Node*next, *back;
};
struct FlowNet {
int S, T, vn;
int d[MAXN], vd[MAXN];
Node Edge[MAXM], *ecnt, *adj[MAXN];
FlowNet() { ecnt=Edge; }
void init(int a, int b, int c) {
S = a; T = b; vn = c;
}
void addedge(int a, int b, int c) {
(++ecnt)->to = b; ecnt->c = c;
ecnt->next = adj[a]; adj[a] = ecnt;
ecnt->back = ecnt+1;
(++ecnt)->to = a; ecnt->c = 0;
ecnt->next = adj[b]; adj[b] = ecnt;
ecnt->back = ecnt-1;
}
int aug(int u, int augco)
{
if (u == T) return augco;
int augc = augco, mind = vn-1, delta;
for (Node*p = adj[u]; p; p=p->next)
if (p->c > 0) {
if (d[u] == d[p->to]+1) {
delta = aug(p->to, Min(p->c, augc));
augc -= delta;
p->c -= delta;
p->back->c += delta;
if (d[S]>=vn) return augco-augc;
if (!augc) break;
}
mind = Min(mind, d[p->to]);
}
if (augc == augco) {
if (!--vd[d[u]]) d[S] = vn;
++vd[d[u] = mind+1];
}
return augco - augc;
}
int ISAP()
{
int flow = 0;
clear(d); clear(vd);
vd[0] = vn;
while (d[S] < vn) flow+=aug(1, INF);
return flow;
}
} G;
int N, M;
int main()
{
int a, b, c;
scanf("%d%d", &M, &N);
G.init(1, N, N);
for (int i = 1; i<=M; ++i)
{
scanf("%d%d%d", &a, &b, &c);
G.addedge(a, b, c);
}
printf("%d
", G.ISAP());
return 0;
}
第K短路-K-th_Short
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXM 100005
#define MAXN 1005
const int INF = 1<<28;
int N, M, S, T, K;
struct Node {
int to, len; Node *next;
}Edge[MAXM*4], *ecnt = Edge, *adj[MAXN], *radj[MAXN];
void addedge(int a, int b, int c)
{
++ecnt;
ecnt->to = b;
ecnt->len = c;
ecnt->next = adj[a];
adj[a] = ecnt;
++ecnt;
ecnt->to = a;
ecnt->len = c;
ecnt->next = radj[b];
radj[b] = ecnt;
}
struct dijs {
int u, dis;
dijs () {}
dijs (int a,int b) {u=a; dis=b;}
bool operator < (const dijs&a) const {
return dis > a.dis;
}
};
int rdis[MAXN];
bool vis[MAXN];
priority_queue<dijs> dij;
void rDijkstra() //边反向跑最短路以获取H函数值
{
memset(rdis, 0x3f, sizeof rdis);
rdis[T] = 0;
dij.push(dijs(T, 0));
dijs t;
while (!dij.empty()) {
t = dij.top(); dij.pop();
if (vis[t.u]) continue;
vis[t.u] = 1;
for (Node *p = radj[t.u]; p; p=p->next)
if (rdis[p->to] > t.dis + p->len) {
rdis[p->to] = t.dis + p->len;
dij.push(dijs(p->to, rdis[p->to]));
}
}
}
struct ss {
int u, pre;
ss () {}
ss (int a, int b) { u=a; pre=b; }
bool operator < (const ss&a) const {
return pre+rdis[u] > a.pre+rdis[a.u]; //pre是G函数值，rdis是H函数值，根据两个之和判定优先级。
}
};
int Tvisn; //第几次到达T点
priority_queue<ss> as;
int Astar()
{
if (S==T) Tvisn = -1; //如果起点终点相等，一开始不算到达终点
as.push(ss(S, 0));
ss t;
while (!as.empty()) {
t = as.top();
as.pop();
if (t.u == T) {
++Tvisn;
if (Tvisn == K) return t.pre; //根据A*算法的正确性，第K次到达即为第K短路
}
for (Node *p = adj[t.u]; p; p=p->next)
as.push(ss(p->to, t.pre + p->len));
}
return -1;
}
int main()
{
int i, a, b, c;
scanf("%d%d", &N, &M);
for (i = 1; i<=M; ++i)
{
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
scanf("%d%d%d", &S, &T, &K);
rDijkstra();
printf("%d
", Astar());
return 0;
}
Time: 2017-10-16