hpc模板

最大m子段和----------------------------------------------------------------------------------------2 整数划分-----------------------------------------------------------------------------------------------3 一遍扫描求前后第一个出现的比这个数小的数-----------------------------------------------5 筛选法求素数-----------------------------------------------------------------------------------------5 求一个数组里面最大值与最小值得差不大于M的最大长度-------------------------------6 求n的阶乘里面的素数因子的个数--------------------------------------------------------------7 排列的生成--------------------------------------------------------------------------------------------7 连分数--------------------------------------------------------------------------------------------------7 扩展欧几里德-----------------------------------------------------------------------------------------7 计算catalan数----------------------------------------------------------------------------------------8 集合DP的框架--------------------------------------------------------------------------------------9 Dilworth定理-----------------------------------------------------------------------------------------10 后缀数组-----------------------------------------------------------------------------------------------11 最长公共递增子序列--------------------------------------------------------------------------------14 N Queens Problem------------------------------------------------------------------------------------15 kmp匹配-----------------------------------------------------------------------------------------------17 堆实现的dij-------------------------------------------------------------------------------------------19 最小权顶点覆盖--------------------------------------------------------------------------------------21 最大密度子图----------------------------------------------------------------------------------------- 23 第K最短路--------------------------------------------------------------------------------------------26 最小费用最大流---------------------------------------------------------------------------------------28 最大流---------------------------------------------------------------------------------------------------32 树所有点的最远距离---------------------------------------------------------------------------------34 朱 --- 刘 算法求最小树形图-----------------------------------------------------------------------36 生成树的计数-------------------------------------------------------------------------------------------39 RMQ------------------------------------------------------------------------------------------------------41 LCA-------------------------------------------------------------------------------------------------------42 有向图的强连通分量----------------------------------------------------------------------------------42 半连通分量的判定--------------------------------------------------------------------------------------44 婚配问题--------------------------------------------------------------------------------------------------46 最小平均割边集-----------------------------------------------------------------------------------------48 最大匹配---------------------------------------------------------------------------------------------------50 最佳匹配----------------------------------------------------------------------------------------------------51 最优比率生成树-------------------------------------------------------------------------------------------54 度限制生成树----------------------------------------------------------------------------------------------56 最小生成树-------------------------------------------------------------------------------------------------59 双连通分量-------------------------------------------------------------------------------------------------60 割点---------------------------------------------------------------------------------------------------------- 60 欧拉回路-----------------------------------------------------------------------------------------------------64 凸包-----------------------------------------------------------------------------------------------------------64 高精度--------------------------------------------------------------------------------------------------------66 高斯消元-----------------------------------------------------------------------------------------------------71 Treap-----------------------------------------------------------------------------------------------------------74 排列------------------------------------------------------------------------------------------------------------80

最大m子段和 /*

经典DP问题:最大m子段和 num[j]:序列中的第j个数．

dp[i][j]:在序列的前j个数中找i个局部和所得到的最大总和．

t[i][j]:在序列的前j个数中找i个局部和并且最后一个局部和必须包含num[j]所得到的最大总和．

因为num[j]可以在一个局部和里，也可以不在一个局部和里，所以有 dp[i][j]=max{t[i][j],dp[i][j-1]}.

因为num[j]可以自己组成一个局部和或者可以跟它前面的数组成一个局部和，所以有t[i][j]=max{dp[i-1][j-1]+num[j], t[i][j-1]+num[j]}. */

#include #include

const int NN = 1000005; int dp[2][NN],t[NN]; int m,n,num[NN];

int max( int x,int y ) { return x>y?x:y; }

void maxSum( int m,int n,int num[] ) { int i,j,now=0,total=0;

// for( i=1; i<=n; i++ ) dp[0][i] = 0; memset( dp,0,sizeof(dp) ); for( i=1; i<=m; i++ ){ now = 1-now; total += num[i]; dp[now][i] = t[i] = total; for( j=i+1; j<=n; j++ ){ t[j] = max( dp[1-now][j-1],t[j-1] )+num[j]; dp[now][j] = max( dp[now][j-1],t[j] ); } } printf(\}

int main() { int i; while( scanf(\ for( i=1; i<=n; i++ ) scanf(\

2

maxSum( m,n,num ); } return 0; }

/*整数划分*/

////////////////////////////////////////////////////////////////////////////////////////// 可以参考组合数学page183 Input

每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)

Output

对于每组输入，请输出六行。

第一行： 将n划分成若干正整数之和的划分数。 f(i,j) 表示把i分成最大值为j的fen法 f(i,j) = f(i-j,j)+f(i,j-1); 初始化：f(0,i) = 1;

组合数学page183把n个无区别的球放进m个无区别的盒子允许空盒！第二行： 将n划分成k个正整数之和的划分数。 f(n-k,k)相当于整数n-k用不大于k的数来拆分

第三行： 将n划分成最大数不超过k的划分数。 f(n,k)

第四行： 将n划分成若干奇正整数之和的划分数。(母函数处理)

第五行： 将n划分成若干不同整数之和的划分数。 f(i,j)意义同上 f(i,j) = f(i-j,j-1)+f(i,j-1)

第六行： 打印一个空行。

Sample Input 5 2

Sample Output 7 2 3

3

3 3

/////////////////////////////////////////////////////////////////////////////////////////// #include #include #define MAXN 10

int dp1[MAXN][MAXN], dp2[MAXN][MAXN], dp3[MAXN][MAXN], dp4[MAXN][MAXN], dp5[MAXN][MAXN], ans[MAXN],tmp[MAXN];

void create() { int i,j,k; memset(dp1,0,sizeof(dp1)); for(i=0; i

4

memcpy(tmp,ans,sizeof(tmp)); }//将n划分成若干奇正整数之和的划分数。 memset(dp5,0,sizeof(dp5)); dp5[0][0] = 1; for(i=0; i

int main() { int n,k; create(); while(scanf(\ printf(\ } return 0; }

/*一遍扫描求前后第一个出现的比这个数小的数*/ void preDeal() { int i,j; prev[1] = 0; for( i=2; i<=n; i++ ){ j = i-1; while( j>=1&&a[j]>=a[i] ) j = prev[j]; prev[i] = j; } next[n] = n+1; for( i=n-1; i>=1; i-- ){ j = i+1; while( j<=n&&a[j]>=a[i] ) j = next[j]; next[i] = j; } }

/*筛选法求素数*/ #define N 10000 int s[N+1]; void table()

5

{ int i,j; for(i=2; i<=n; i++) s[i] = 1; s[1] = 0; for(i=2; i*i<=N; i++)if(s[i]) for(j=i+i; j<=n; j+=i) s[i] = 1; } /*

求一个数组里面最大值与最小值得差不大于M的最大长度 维护两个队列： increase[] 和 decrease[]

increase[]队列里面的元素为增序 实际上是保存的是下标 decrease[]队列里面的元素为减序 对右边界进行扫描，

当第 i 个元素进队的时候，保证两队列的增，减序性质不变，

即对increase[]队列保持增序，若不满足，则不断的弹，直至满足为止 对decrease[]队列保持减序，若不满足，则不断的弹，直至满足为止

每进一个队列，比较队首元素之差是否小于等于M，若是则更新ans，否则不断的从队首弹出

较小元素，更新start（开始位置），直至满足为止！ */

void find() { int i,start,f1,t1,f2,t2,ans; f1 = t1 = f2 = t2 = 1; ans = 0; start = 0; for( i=1; i<=N; i++ ){ while( dist[increase[t1-1]]>dist[i] && t1>f1 ) t1--; //保持队列性质 increase[t1++] = i; while( dist[decrease[t2-1]]f2 ) t2--;//保持队列性质 decrease[t2++] = i; while( dist[decrease[f2]]-dist[increase[f1]]>M ){ //出队列 start = min(decrease[f2],increase[f1]); if( increase[f1] < decrease[f2] ) f1++; else f2++; } ans = max(ans,i-start); } printf(\} /*

6

求n的阶乘里面的素数因子的个数 */

1.构造素数表 s[] void find（int n） { int tmp; for（i=2; i<=n; i++）{ tmp = n; if(s[i]) while(tmp){ t[i] += tmp/i; tmp /=i; } } }

/*排列的生成*/ sort(a,a+n); do{ for( i=1; i<=n; i++ ) printf(\

}while( next_permutation(a,a+n) ); 数组a是已经排过序了的！

输出排列是字典顺序从小到大！ /*连分数*/ void work() { int p, q, p1, q1, p2, q2; p = 0; q = 1; p1 = 1; q1 = n; printf(\ printf(\ while (p1 != q1) { p2 = (q + n) / q1 * p1 - p; q2 = (q + n) / q1 * q1 - q; printf(\ p = p1; q = q1; p1 = p2; q1 = q2; } }

/*扩展欧几里德*/

//返回 a，b的最大公约数，并使 ax+by = d，d为 gcd（a，b）//递归出口 b==0； a*1 + 0*0 = d //当前层已知 bx+(a%b)*y = d

7

//令 x = y;

// y = x-(a/b)*y;

//有 ax+by = ay+bx-b*(a/b)*y = bx+(a%b)*y = d;成立

int extEuclid( int a,int b,int &x,int &y ) { if( b==0 ){ x = 1; y = 0; return a; } int d,tmp; d = extEuclid( b,a%b,x,y ); tmp = x; x = y; y = tmp-a/b*y; return d; } /*

计算catalan数 */

问题等价于：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？

方法：递推+求组合数 令h(1)＝1，满足

h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2) 该递推关系的解为：h(n)=c(2n,n)/(n+1) (n=1,2,3,...)

同类问题有：

(1)矩阵链乘： P=a1×a2×a3×??×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

(2)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) (3)将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数?

这样的数也叫Calatan数

计算中，对组合数的求解要避免不要超过精度范围

#include using namespace std;

int C(int a,int b)

8

{

int i;

int totle=1; int temp=a;

for(i=1;i<=b;i++) {

totle=totle*temp/i; temp--; }

return totle; }

int catalan(int n) {

return C(2*n,n)/(n+1) }

int main() {

int test,n; cin>>test; while(test--) {

cin>>n;

cout<

集合DP的框架 */ //后推

void slove() { int i,j,m,k,x; memset(best,0,sizeof(best)); m = (1<

9

ans = 0; for( i=1; i<=n; i++ ) ans = max( ans,best[m][i] ); printf(\}

//前推

void slove() { int i,j,k,m,ans,tmp,Max; m = (1<

/*Dilworth定理 */

导弹拦截问题－偏序集的Dilworth 导弹拦截是一个经典问题：

求一个序列的最长不上升子序列，以及求能最少划分成几组不上升子序列。 第一问是经典动态规划，第二问直接的方法是最小路径覆盖，但是二分图匹配的复杂度较高， 我们可以将其转化成求最长上升子序列，其最大值即等于不上升子序列的最小划分数。 这就涉及到组合数学中偏序集的Dilworth定理。（第二问的贪心方法其实就是这个定理的证明过程）

先介绍一下偏序关系：

偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”），它满足自反性、反对称性和传递性。

即，对于X中的任意元素a,b和c，有:

10

自反性：a≤a;

反对称性：如果a≤b且b≤a，则有a=b; 传递性：如果a≤b且b≤c，则a≤c 。

带有偏序关系的集合称为偏序集。

令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。

在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。 一个反链A是X的一个子集，它的任意两个元素都不能进行比较。 一个链C是X的一个子集，它的任意两个元素都可比。

下面是两个重要定理：

定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。

其对偶定理称为Dilworth定理：

定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。 证明：设p为最少反链个数

(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。

(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3??最终，会有一个Xk非空而X(k+1)为空。于是A1,A2,...,Ak就是X的反链的划分，同时存在链a1<=a2<=...<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。因此r=p，定理1得证。

回过头来看导弹拦截第二问。我们定义偏序关系≤：a≤b表示a出现不迟于b且a的值不小于b的值。

这个偏序集的最长反链即最长上升子序列，它的不上升子序列是偏序集的链。 由Dilworth定理可知，不上升子序列的最小划分数＝最长上升子序列的长度。

p.s. 这里的贪心方法是，每次选出所有的在它前面没有大于或等于它的数作为一组。

其实我们每次选的是偏序集的最小元，因此我们最终得到的答案就是上面的k。由r<=p及r>=k>=p可以得到r=k=p，因此贪心正确。 /*

pku3261：典型的后缀数组！ */

#include

11

#include #include

using namespace std; const int NN = 40005; int Sa[NN], //后缀数组 Rank[NN], //名次数组 LstRank[NN], //上一次的名次数组 Height[NN], //Height[i] = LCP( i,i-1 ) = lcp( suffix(i),suffix(i-1) ); d;

int a[NN],N,K;

int dp[NN][20]; //Sparse Table算法初始化数组 bool cmpA( int x,int y ) { return a[x]

bool cmpLstRank( int x,int y ) { return LstRank[x]

void input() { int i; memset( a,-1,sizeof(a) ); for( i=1; i<=N; i++ ) scanf(\ }

void suffixArray() { int i,j; for( i=1; i<=N; i++ ) Sa[i] = i; sort( Sa+1,Sa+1+N,cmpA ); //第一次排序，排序后Sa中是按元素从小到大 for( j=1,i=1; i<=N; i++ ){ if( i>1&&a[Sa[i]]!=a[Sa[i-1]] ) j++; //后缀数组Sa中两个值不相等 Rank[Sa[i]] = j; } //以下是用倍增思想求后缀数组，倍增思想也就是利用前面的Rank数组（大小关系反映了后缀）求现在的Sa for( d=1; d<=N&&Rank[Sa[N]]1&&cmpLstRank(Sa[i-1],Sa[i]) ) j++; Rank[Sa[i]] = j;

12

} } }

void getHeight() { int i,k,h; Height[Sa[1]] = 0; //后缀数组中的第一个Height当然为0了，因为它前面没有后缀了！ for( h=0,i=1; i<=N; i++ )if( Rank[i]>1 ){//这里很巧妙，省去了h数组，可以看作是以计算h为顺序的！ k = Sa[Rank[i]-1]; while( a[k+h]==a[i+h] ) h++; Height[Rank[i]] = h; if( h>0 ) h--; } }

int min( int x,int y ) { return x

void RMQ()

{//sparse table，要注意边界，包含端点问题 int i,j; for( i=1; i<=N; i++ ) dp[i][0] = Height[i]; for( j=1; (1<

int query( int i,int j ) { int t = 0; int len = j-i+1; while( len ){ t++; len>>=1; } t--; return min( dp[i][t],dp[j-(1<

void slove() { int i,t,ans; ans = 0; for( i=2; i+K-2<=N; i++ ){ t = query( i,i+K-2 ); if( t>ans ) ans = t; } printf(\

13

}

int main() { while( scanf(\ input(); suffixArray(); getHeight(); RMQ(); slove(); } return 0; } /*

pku2127最长公共递增子序列 */

#include #include const int NN = 505;

int n,m,a[NN],b[NN],ans[NN],dp[NN],f[NN][NN];

void GCIS() { int i,j,k,Max; memset( dp,0,sizeof(dp) ); for( i=0; i<=n; i++ ) f[0][i] = 0; for( i=0; i<=m; i++ ) f[i][0] = 0; for( i=1; i<=m; i++ ){ k = 0; for( j=1; j<=n; j++ ){ f[i][j] = f[i-1][j]; if( b[j]dp[k] ) k = j; else if( b[j]==a[i]&&dp[k]+1>dp[j] ){ dp[j] = dp[k]+1; f[i][j] = i*(n+1)+k; } } } for( Max=i=1; i<=n; i++ )if( dp[i]>dp[Max] ) Max = i; for( i=m*(n+1)+Max,j=dp[Max]; j; i=f[i/(n+1)][i%(n+1)],j-- ) ans[j] = b[i%(n+1)]; printf(\ for( i=1; i<=dp[Max]; i++ ) if( i==dp[Max] ) printf(\

14

else printf(\}

int main() { int i; scanf(\ for( i=1; i<=m; i++ ) scanf(\ scanf(\ for( i=1; i<=n; i++ ) scanf(\ GCIS(); return 0; }

// N Queens Problem

// 试探-回溯算法，递归实现 #include #include #include

// sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。 long sum = 0, upperlim = 1;

// 试探算法从最右边的列开始。 void test(long row, long ld, long rd) { if (row != upperlim){ // row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0， // 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1。 // 也就是求取当前哪些列可以放置皇后。 long pos = upperlim & ~(row | ld | rd); while (pos){// 0 -- 皇后没有地方可放，回溯。 // 拷贝pos最右边为1的bit，其余bit置0。 // 也就是取得可以放皇后的最右边的列。 long p = pos & -pos; // 将pos最右边为1的bit清零。

// 也就是为获取下一次的最右可用列使用做准备， // 程序将来会回溯到这个位置继续试探。 pos -= p; // row + p，将当前列置1，表示记录这次皇后放置的列。 // (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。 // (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。 // 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归

15

// 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位

// 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线

// 上产生的限制都被记录下来了。 test(row + p, (ld + p) << 1, (rd + p) >> 1); } } else{ // row的所有位都为1，即找到了一个成功的布局，回溯。 sum++; } }

int main() {

time_t tm; int n = 14; tm = time(0);

// 因为整型数的限制，最大只能32位， // 如果想处理N大于32的皇后问题，需要 // 用bitset数据结构进行存储。

if ((n < 1) || (n > 32)) {

printf(\只能计算1-32之间\\n\ exit(-1); }

printf(\皇后\\n\

// N个皇后只需N位存储，N列中某列有皇后则对应bit置1。 upperlim = (upperlim << n) - 1;

test(0, 0, 0);

printf(\共有%ld种排列, 计算时间%d秒 \\n\}

////////////uva

#include #include

int sum = 0, upperlim = 1; int ans[20];

16

char str[20][20];

void test(int row, int ld, int rd,int lev) { int i; if (row != upperlim){ int pos = upperlim & ~(row | ld | rd); while (pos){ for( i=0; !((1<> 1,lev+1); } } else{ sum++; } }

int main() {

int i,n,t=0; while( 1 ){ scanf(\ if( n==0 ) break; getchar(); for( i=0; i

/*kmp匹配*/ #include #include #define MAXN 1000

17

#define N 100 int next[N];

void getnext(char s[])

{//找到子串的next数组，即自身与自身的匹配 int i,j; i = 0; j = -1; next[0] = -1; while(s[i]){ if(j==-1||s[i]==s[j]){ i++; j++; next[i] = j; } else j = next[j]; } }

int kmp(char m[],char s[])

{//找到子串 s 出现在串 m中的第一个位置，并返回这个位置 int i,j; i = 0; j = 0; while(m[i]){ if(j==-1||m[i]==s[j]){ i++; j++; if(s[j]=='\\0') return i-j; } else j = next[j]; } return -1; }

int main() { char m[MAXN],s[N]; int t,test; scanf(\ while(test--){ scanf(\ getchar(); scanf(\

18

getnext(s); for(t=0; t

堆实现的dij */

#include #include

using namespace std;

const int maxv = 30000+5; const int inf = 999999999;

struct node{ int v, st; node *next; };

struct HEAP{ int no, st; };

node G[maxv];

HEAP heap[maxv*60]; bool used[maxv]; int n, st[maxv];

bool cmp(HEAP a, HEAP b){return a.st>b.st;}

int dij() { int i, t=0; memset(used, 0, sizeof(used)); for(i=1; i<=n; i++) st[i] = inf;

19

heap[0].st = st[1] = 0, heap[t++].no = 1; push_heap(heap, heap+t, cmp); while( !used[n] && t>0 ) { HEAP te = heap[0]; pop_heap(heap, heap+t--, cmp); if( !used[te.no] ) { used[ te.no ] = true; node *tt = G[te.no].next; while( tt ) { if( !used[tt->v] && st[tt->v] > tt->st + st[te.no] ) { st[tt->v] = tt->st + st[te.no]; heap[t].no = tt->v, heap[t++].st = st[tt->v]; push_heap(heap, heap+t, cmp); } tt = tt->next; } } } return st[n]; }

void ins(int v, int w, int st) { node *t = new node; t->v = w, t->next = G[v].next; G[v].next = t, t->st = st; }

int main() { int i, m, v, w, st; scanf(\ memset(G, 0, sizeof(G)); for(i=0; i

20

printf(\ return 0; } /*

pku2125:最小权顶点覆盖！

题目大意: 给定一个有向图，对于每个顶点v，删除接入v的边的花费为W+，删除v接出的边的花费为W-

求将所有边删除所需要的最小费用！ 转化为最小点权覆盖！ 重新建立图: */

#include #include const int NN = 250;

const int INF = 1000000000;

int n,m,in[NN],out[NN];

int cap[NN][NN],flow[NN][NN],que[NN],pre[NN],maxFlow,s,t; bool g[NN][NN]; bool bfs() { int front,tail,i,u; memset( pre,-1,sizeof(pre) ); front = tail = 0; que[tail++] = s; pre[s] = s; while( front0 ){ pre[i] = u; if( i==t ) return true; que[tail++] = i; } } return false; }

void argument() { int u,ex=INF; for( u=t; u!=s; u=pre[u] )if( cap[pre[u]][u]-flow[pre[u]][u]

21

} maxFlow += ex; }

void solve() { int cnt,i; maxFlow = 0; while( bfs() ) argument(); printf(\ for( cnt=0,i=1; i<=n; i++ ){ if( pre[i]==-1 ) cnt++; if( pre[i+n]!=-1 ) cnt++; } printf(\ for( i=1; i<=n; i++ ){ if( pre[i]==-1 ) printf(\ if( pre[i+n]!=-1 ) printf(\ } }

int main() { int i,u,v; while( scanf(\ s = 0; t = n+n+1; memset( cap,0,sizeof(cap) ); memset( flow,0,sizeof(flow) ); memset( g,false,sizeof(g) ); for( i=1; i<=n; i++ ) scanf(\ for( i=1; i<=n; i++ ) scanf(\ for( i=1; i<=m; i++ ){ scanf(\ cap[u][n+v] = INF; g[u][n+v] = true; g[n+v][u] = true; } for( i=1; i<=n; i++ ){ g[s][i] = true; cap[s][i] = out[i]; } for( i=n+1; i<=n+n; i++ ){ g[i][t] = true; cap[i][t] = in[i-n];

22

} solve(); } return 0; } /*

pku3155:最大密度子图，最小割的应用！ max ( |E|/|V| ),借助参数搜索的思想！

设f(g) = max(|E|-g*|V|),知f(g)是一个减函数

因为一条边存在的条件是边的两个顶点存在！于是我们又可以联想到最大权closure! 建图: 对每条边标号ve，对边(u,v)建有向边(u,ve)和(v,ve),点的权重为-g,边的权重为1....

值得注意的地方是,求最大权closure的时候,源点应该和条件进行连边! 参数搜索的时候用的是迭代的方法,非常快! */

#include #include #include

const int NN = 1105; const double EPS = 1e-9; const double INF = 1e99;

struct Edge{ int u,v; }edge[NN];

int s,t,n,m,deg[NN],adj[NN][NN],que[NN],pre[NN],ans[NN]; double up,cap[NN][NN],flow[NN][NN],maxFlow; bool use[NN]; void makeGraph() { int i,u,v; memset( deg,0,sizeof(deg) ); for( i=1; i<=m; i++ ){ cap[i][t] = 1.0; adj[i][deg[i]++] = t; } for( i=1; i<=m; i++ ){ u = edge[i].u+m; v = edge[i].v+m; cap[u][i] = INF; adj[i][deg[i]++] = u; adj[u][deg[u]++] = i; cap[v][i] = INF;

23

adj[i][deg[i]++] = v; adj[v][deg[v]++] = i; } for( i=m+1; i<=m+n; i++ ) adj[s][deg[s]++] = i; }

bool bfs() { int i,u,v,front,tail; front = tail = 0; memset( pre,-1,sizeof(pre) ); que[tail++] = s; pre[s] = s; while( frontEPS ){ pre[v] = u; if( v==t ) return true; que[tail++] = v; } } } return false; }

void argument() { int u; double ex = INF; for( u=t; u!=s; u=pre[u] )if( cap[pre[u]][u]-flow[pre[u]][u]

double process( double p ) { int i,j; for( i=m+1; i<=m+n; i++ ) cap[s][i] = p; for( i=0; i<=m+n+1; i++ ) for( j=0; j<=m+n+1; j++ ) flow[i][j] = 0.0;

24

maxFlow = 0.0; while( bfs() ) argument(); return m*1.0-maxFlow; }

void solve() { double f,cur; int i,cnt,up,down; cur = 0.5; s = 0; t = m+n+1; makeGraph(); do{ f = process( cur ); memset( use,false,sizeof(use) ); for( up=0,i=1; i<=m; i++ )if( pre[i]==-1 ){ up++; use[edge[i].u] = true; use[edge[i].v] = true; } for( down=0,i=1; i<=n; i++ )if( use[i] ) down++; cur = up*1.0/down; }while( fabs(f)>EPS ); for( cnt=0,i=1; i<=n; i++ )if( use[i] ) ans[cnt++] = i; printf(\ for( i=0; i

int main() { int i,u,v; while( scanf(\ if( m==0 ){ printf(\ for( i=1; i<=m; i++ ){ scanf(\ edge[i].u = u; edge[i].v = v; } solve(); } return 0; } /*

非简单路径

25

第K最短路：根据求最短路的原理，每个点最多从堆中出来1次去更新其他的点 那么第K最短路每个点最多从堆中出来K次去更新其他的点，且出现 K次的时候就是源点到该点的前K短路！ */

#include #include #include

using namespace std; #define K 2 #define NN 5005

#define INF 1000000000 struct node{ int v,len; node *nxt; };

node adj[NN]; //邻接表

struct Heap{ int v,len; };

Heap h[20*NN]; //堆 int hn;

struct Path{ int path[K],num; };

Path dis[NN]; //路径 int vn,en;

bool cmp( Heap x,Heap t ) { return x.len>t.len; }

void insert( int u,int v,int w ) { node *p; p = new node; p->v = v; p->len = w; p->nxt = adj[u].nxt; adj[u].nxt = p; }

void slove( int s,int t ) { int i,j,u,v,cur,cost,times=0;

26

Heap tmp,tmp1; //初始化 for( i=1; i<=vn; i++ ) for( j=0; j0 ){ tmp = h[0]; if( tmp.v==t ){// 堆中终点出现一次，次数加一，直到K次为止 times++; if( times==K ) break; } pop_heap( h,h+hn--,cmp ); u = tmp.v; cur = tmp.len; for( node *p=adj[u].nxt; p; p=p->nxt ){ v = p->v; cost = cur+p->len; if( dis[v].num==0 ){ //若扩展节点一次都没有被更新，则直接更新 dis[v].num = 1; dis[v].path[0] = cost; tmp1.v = v; tmp1.len = cost; h[hn++] = tmp1; push_heap( h,h+hn,cmp ); //进堆 } else{ sort( dis[v].path,dis[v].path+dis[v].num ); //对路径长度进行排序 i = lower_bound( dis[v].path,dis[v].path+dis[v].num,cost )-dis[v].path; //找到最接近cost的值 if( i>=K||dis[v].path[i]==cost ) continue;//若比前K个路径值都大 或者 （状态已经出现）过则不必理会 if( dis[v].num

27

} } sort( dis[t].path,dis[t].path+dis[t].num ); printf(\}

int main() { int u,v,w,i; scanf(\ for( i=1; i<=vn; i++ ) adj[i].nxt = NULL; while( en-- ){ scanf(\ insert( u,v,w ); insert( v,u,w ); } slove( 1,vn ); return 0; }

/* 最小费用最大流*/ #include #include

const int NN = 60;

const int INF = 10000000;

struct NetNode{ int v,f, //流量 cap, //容量 cost; //单位流量的费用 NetNode *next, *rev; //反向边 }net[2*NN];

struct PathNode{ //路径节点，找增广路的时候用的 int pre, //前驱 fx, //可增量 cost; //费用 NetNode *edge; }path[2*NN];

int n,N,M,K,order[NN][NN],store[NN][NN],cost[NN][NN][NN]; int s,t,minCost,maxFlow,que[NN*NN*NN]; bool use[2*NN];

int min( int x,int y ) { return x

28

{ NetNode *p,*q; p = new NetNode; p->v = v; p->f = 0; p->cap = cap; p->cost = cost; p->next = net[u].next; net[u].next = p; q = new NetNode; q->v = u; q->f = 0; q->cap = 0; q->cost = -cost; q->next = net[v].next; net[v].next = q; p->rev = q; q->rev = p; }

bool spfa()

{//spfa找增广路 int front,tail,i,u,fx; front = tail = 0; for( i=0; i<=n; i++ ){ path[i].pre = i; path[i].fx = INF; path[i].cost = INF; path[i].edge = NULL; } path[s].cost = 0; memset( use,false,sizeof(use) ); que[tail++] = s; use[s] = true; while( frontnext ){ fx = p->cap-p->f; if( fx>0&&path[u].cost+p->costv].cost ){ path[p->v].pre = u; path[p->v].fx = min( fx,path[u].fx ); path[p->v].cost = path[u].cost+p->cost; path[p->v].edge = p; if( !use[p->v] ){ que[tail++] = p->v; use[p->v] = true; } } } } if( path[t].cost==INF ) return false; return true; }

29

/*

bool bellman()

{//bellman找增广路 int i,fx; bool flag = true; NetNode *p; for( i=0; i<=n; i++ ){ path[i].pre = -1; path[i].fx = path[i].cost = INF; } path[0].pre = 0; path[0].cost = 0; while( flag ){ flag = false; for( i=0; i<=n; i++ )if( path[i].cost!=INF ) for( p=net[i].next; p; p=p->next ){ fx = p->cap - p->f; if( fx>0&&path[i].cost+p->costv].cost ){ flag = true; path[p->v].cost = path[i].cost+p->cost; path[p->v].pre = i; path[p->v].edge = p; path[p->v].fx = min( fx,path[i].fx ); } } } if( path[t].cost!=INF ) return true; return false; } */

void argument() { int u,fx=path[t].fx; for( u=t; u!=s; u=path[u].pre ){ path[u].edge->f += fx; path[u].edge->rev->f = -path[u].edge->f; minCost += fx*path[u].edge->cost; } maxFlow += fx; }

void mcmf() { maxFlow = 0;

// while( bellman() ) argument(); while( spfa() ) argument(); }

void solve()

30

{ int i,j,k; s = 0; n = t = M+N+1; maxFlow = minCost = 0; for( i=1; i<=K; i++ ){ for( j=0; j<=n; j++ ) net[j].next = net[j].rev = NULL; for( j=1; j<=M; j++ ) insert( s,j,store[j][i],0 ); for( j=1; j<=M; j++ ) for( k=1; k<=N; k++ ) insert( j,M+k,store[j][i],cost[i][k][j] ); for( j=1; j<=N; j++ ) insert( M+j,t,order[j][i],0 ); mcmf(); } printf(\}

int main() { int i,j,k,need,apply; bool flag; while( 1 ){ scanf(\ if( N==0&&M==0&&K==0 ) break; for( i=1; i<=N; i++ ) for( j=1; j<=K; j++ ) scanf(\ for( i=1; i<=M; i++ ) for( j=1; j<=K; j++ ) scanf(\ flag = true; for( i=1; i<=K; i++ ){ for( need=0,j=1; j<=N; j++ ) need += order[j][i]; for( apply=0,j=1; j<=M; j++ ) apply += store[j][i]; if( apply

31

solve(); } return 0; } /**

* //////////////////

* // MAXIMUM FLOW // * ////////////////// * **/

/****************

* Maximum flow * (Dinic's on an adjacency list + matrix) ****************

* Takes a weighted directed graph of edge capacities as an adjacency * matrix 'cap' and returns the maximum flow from s to t. *

* PARAMETERS:

* - cap (global): adjacency matrix where cap[u][v] is the capacity * of the edge u->v. cap[u][v] is 0 for non-existent edges. * - n: the number of vertices ([0, n-1] are considered as vertices). * - s: source vertex. * - t: sink. * RETURNS: * - the flow

* - prev contains the minimum cut. If prev[v] == -1, then v is not * reachable from s; otherwise, it is reachable. * RUNNING TIME: * - O(n^3) * FIELD TESTING:

* - Valladolid 10330: Power Transmission (Gives WA, but it's probably my graph building that's wrong)

* - Valladolid 563: Crimewave

* - Valladolid 753: A Plug for UNIX * - Valladolid 10511: Councilling

* - Valladolid 820: Internet Bandwidth * - Valladolid 10779: Collector's Problem * #include **/

#include #include

// the maximum number of vertices

32

#define NN 1024

// adjacency matrix (fill this up)

int cap[NN][NN], deg[NN], adj[NN][NN];

// BFS stuff

int q[NN], prev[NN];

int dinic( int n, int s, int t ) {

int u,v,i,z,flow = 0; while( true ) {

memset( prev, -1, sizeof( prev ) ); int qf = 0, qb = 0;

prev[q[qb++] = s] = -2;

while( qb > qf && prev[t] == -1 )

for( u = q[qf++], i = 0, v; i < deg[u]; i++ )

if( prev[v = adj[u][i]] == -1 && cap[u][v] ) prev[q[qb++] = v] = u; if( prev[t] == -1 ) break;

for( z = 0; z < n; z++ ) if( cap[z][t] && prev[z] != -1 ) {

int bot = cap[z][t];

for( v = z, u = prev[v]; u >= 0; v = u, u = prev[v] ) if( cap[u][v]

cap[z][t] -= bot; cap[t][z] += bot;

for( v = z, u = prev[v]; u >= 0; v = u, u = prev[v] ) {

cap[u][v] -= bot; cap[v][u] += bot; }

flow += bot; } }

return flow; }

//----------------- EXAMPLE USAGE -----------------

33

int main() {

// read a graph into cap[][] memset( cap, 0, sizeof( cap ) ); int n, s, t, m;

scanf( \ while( m-- ) {

int u, v, c; scanf( \ cap[u][v] = c; }

// init the adjacency list adj[][] from cap[][] memset( deg, 0, sizeof( deg ) ); for( int u = 0; u < n; u++ )

for( int v = 0; v < n; v++ ) if( cap[u][v] || cap[v][u] ) adj[u][deg[u]++] = v;

printf( \ return 0; } /*

树所有点的最远距离

求所有点的最远距离.树状DP求,down[i]表示以i为根的子树的最大深度,top[i]表示从i点向上的最远距离,然后借助父亲节点和孩子节点可以比较容易地O(n)时间内求出. */

pku3162的前半部分 #include #include

#define MAXN 1000000+5 struct node{ node *next; int v,w, first, //节点最深的孩子 second; //节点最第二深的孩子 };

int N,M,top[MAXN], //节点向上的最远距离 dist[MAXN]; //节点的最远距离 bool visit[MAXN]; //标记数组 node graph[MAXN]; //邻接表建图

34

int max(int x,int y) { return x>y?x:y; }

void insert(int u,int v,int w) { node *p; p = new node; p->v = v; p->w = w; p->first = p->second = 0; p->next = graph[u].next; graph[u].next = p; }

void init() { int i,u,w; for(i=1; i<=N; i++){ graph[i].next = NULL; graph[i].v = i; graph[i].w = 0; graph[i].first = graph[i].second = 0; } for(i=2; i<=N; i++){ scanf(\ insert(i,u,w); insert(u,i,w); } }

void dfs(int s) { node *t; visit[s] = 1; for( t=graph[s].next; t; t=t->next )if( !visit[t->v] ){ dfs( t->v ); if( graph[t->v].first+t->w > graph[s].first ){ graph[s].second = graph[s].first; graph[s].first = graph[t->v].first+t->w; } else if( graph[t->v].first+t->w > graph[s].second ){ graph[s].second = graph[t->v].first+t->w; } } }

void DFS(int s) { node *t;

35

visit[s] = 1; for( t=graph[s].next; t; t=t->next )if( !visit[t->v] ){ if( graph[t->v].first+t->w != graph[s].first) //如果节点不在其父亲节点的最大深度的路径上，则top 由它的父亲节点的最深路径和top[父亲]决定 top[t->v] = max( graph[s].first, top[s] )+t->w; else//如果节点不在其父亲节点的最大深度的路径上，则top 由它的父亲节点的次深路径和top[父亲]决定 top[t->v] = max( graph[s].second, top[s] )+t->w; DFS( t->v ); } }

int main() { int i; while( scanf(\ init(); //建图 memset(visit,0,sizeof(visit)); dfs(1); //第一遍dfs求出最大和次大深度孩子 // printf(\// for(i=1; i<=N; i++) // printf(\ memset(visit,0,sizeof(visit)); top[1] = 0; // down[1] = graph[1].first; DFS(1); //第二遍dfs求出top[]数组 for(i=1; i<=N; i++) dist[i] = max( graph[i].first, top[i] ); // for(i=1; i<=N; i++) // printf(\// printf(\ } return 0; } /*

朱 --- 刘 算法求最小树形图

步骤： 1 。。判连通，并找到根（入度为0的点） 2 。。寻找和各顶点相连的最小边，如果没环，则找到 3 。。缩圈，缩圈的过程中巧妙的处理了权值，避免了展圈,转2

时间复杂度： O （ n*m ） */

#include #include

36

#define MAXN 101

#define maxint (1<<31-1)

int graph[MAXN][MAXN], //邻接矩阵 list[MAXN][MAXN]; //圈

int no[MAXN],prev[MAXN],minedge[MAXN],temp[MAXN]; bool mark[MAXN];

int n,head,cost,m,dfs_count; bool found; void select()

{// 寻找和各顶点相连的最小边 int i,j; for(i=1;i=0) { if(graph[i][j]

void append(int a,int b)

{// 把圈 a 或者 点a 合并到圈 b 或者是点 b int i; for(i=1;i<=list[a][0];i++) { list[b][0]++; list[b][list[b][0]]=list[a][i]; no[list[a][i]]=b; } list[a][0]=0; //合并之后 a 圈 的阶变为0 }

void go(int id)

{//从 id 出发找圈 int i,j,s; if(mark[id]) {// 路径上的点已经被标记了，因此说明已经找到了一个圈 found=true; s=id; memcpy(temp,no,sizeof(no)); do {

37

cost+=minedge[id]; // cost 加上了圈内的与每个顶点相连的边的最小值 id=prev[id]; if(id!=s)append(id,s); }while(id!=s); for(j=1;j=0) // 圈外的点 ，并且有边存在 graph[i][j]-=minedge[temp[j]]; // 修改 } } mark[id]=true; for(i=0;i

int mincost() { int i; bool stop; // stop为false的时候表示还有圈 cost=0; for(i=0;i0) { found=false; head=i; go(i); //从 i 出发找圈 if(found)stop=false; } }while(stop!=true); for(i=0;i=0)cost+=minedge[i]; return cost;

38

}

void dfs(int r) {// 判断连通 int i; dfs_count++; no[r]=1; for(i=0;i=0)dfs(i); }

void solve() { int ans; dfs_count=0; memset(no,0,sizeof(no)); dfs(0); // 判断连通 if(dfs_count

bool input() {// 建图 int i,k,j; memset(graph,0xffff,sizeof(graph)); scanf(\ if(n==0&&m==0)return false; while(m--) { scanf(\ i--;j--; graph[i][j]=k; } return true; }

int main() { while(input()) solve(); return 0; } /*

生成树的计数 */

#include #include

39

#include const int NN = 15;

const double EPS = 1e-8; int n;

double a[NN][NN];

int findLine(int i,double a[][NN])

{//找出行(i,,,n)、列为i的最大主元素所在的行,并返回行值

int j,maxline=i; //maxline为最大元素所在的行

double max=a[i][i]; //max为最大元素的值 for( j=i+1; jmax ){ max = fabs(a[j][i]); maxline = j; }

return maxline; }

void swapLine( int line,int otherline )

{//交换两行的从line列到n列的元素 int i;double tmp; for( i=line; i

a[line][i]=a[otherline][i]; a[otherline][i]=tmp; } }

void clearNum( int i,double a[][NN] ) {//消去第i列、i行以下的元素 int line=i,j; double tmp;

for( i=i+1; i

tmp=-a[i][line]/a[line][line]; for( j=line; j

a[i][j]=a[i][j]+tmp*a[line][j]; } }

double calDet( double a[][NN] ) {//计算行列式的值

double det=1.0;int i,j; for( i=0; i

j=findLine(i,a); if(i!=j){

swapLine(i,j); det=-1.0*det; };

if( fabs(a[i][i])

40

return 0.0;

det = det*a[i][i]; clearNum(i,a); }

return det; }

int main() { int cas,i,j; scanf(\ while( cas-- ){ scanf(\ for( i=0; i

/* RMQ*/ void RMQ()

{//sparse table，要注意边界，包含端点问题 int i,j; for( i=1; i<=N; i++ ) dp[i][0] = Height[i]; for( j=1; (1<

int query( int i,int j ) { int t = 0; int len = j-i+1;

41

while( len ){ t++; len>>=1; } t--; return min( dp[i][t],dp[j-(1<

/*LCA*/ void init()

{//dp[i][j]表示的是第i个顶点的 第2^j个祖先！,L[]是层数 int i,j; memset( dp,-1,sizeof(dp) ); for( i=1; i<=n; i++ ) dp[i][0] = father[i]; for( j=1; (1<

int LCA(int u,int v ) { int log,i; if( L[u]=0; i-- )if( L[u]-(1<=L[v] ) u = dp[u][i]; if( u==v ) return u; for( i=log; i>=0; i-- ) if( dp[u][i]!=-1&&dp[v][i]!=-1&&dp[u][i]!=dp[v][i] ) u = dp[u][i],v = dp[v][i]; return dp[u][0]; }

/*有向图的强连通分量，tarjan算法*/ 邻接表实现

#include #include

#define MAXN 100

typedef struct node{ int v; node *next; }link;

42

link g[MAXN];

int n, //顶点数 m, //边数 pre[MAXN], //顶点编号数组 low[MAXN], //相当于高度数组 sc[MAXN], //强连通数组 s[MAXN], //栈 cnt0, //标号计数器 cnt1, //强连通分量计数 top; //栈顶指针

void create() { int i,u,v; link *p; memset(g,0,sizeof(g)); for(i=0; iv = v; p->next = g[u].next; g[u].next = p; } }

void SCdfs(int w) { int u,min; link *t; pre[w] = low[w] = min = cnt0 ++;; s[top++] = w; for(t=g[w].next; t; t=t->next){ if(pre[t->v] == -1) SCdfs(t->v); if( low[t->v] < min ) min = low[t->v]; } if(min < low[w]){ low[w] = min; return; } do{

43

u=s[--top]; sc[u] = cnt1; low[u] = n; }while(s[top] != w); cnt1 ++; }

void tarjan() { int i; memset(pre,-1,sizeof(pre)); top = cnt0 = cnt1 = 0; for(i=0; i

int main() { int i; while(scanf(\ create(); tarjan(); for(i=0; i

半连通分量的判定 1)缩点

2)对于缩点后的图判断最长路中是否包含了所有的顶点！*/

#include #include #include

using namespace std; const int NN = 1005; int n,m;

vector g[NN],G[NN];

int deg[NN],edge[NN*6][2],que[NN],front,tail,dp[NN]; int cnt0,cnt1,top,stack[NN],sc[NN],pre[NN],low[NN]; void SCdfs( int u ) { int i,v,min;

44

min = pre[u] = low[u] = cnt0++; stack[top++] = u; for( i=0; i

bool tarjan() { int i,u,v,len; memset( pre,-1,sizeof(pre) ); cnt0 = cnt1 = top = 0; for( i=1; i<=n; i++ )if( pre[i]==-1 ) SCdfs( i ); for( i=1; i<=m; i++ ){ u = edge[i][0]; v = edge[i][1]; if( sc[u]!=sc[v] ){ G[sc[u]].push_back( sc[v] ); deg[sc[v]]++; } } len = front = tail = 0; memset( dp,0,sizeof(dp) ); for( i=0; idp[v] ) dp[v] = dp[u]+1;

45

deg[v]--; if( deg[v]==0 ) que[tail++] = v; } } for( i=0; ilen ) len = dp[i]; for( i=0; i

int main() { int cas,i,u,v; scanf(\ while( cas-- ){ scanf(\ for( i=1; i<=m; i++ ){ scanf(\ edge[i][0] = u; edge[i][1] = v; g[u].push_back( v ); } if( tarjan() ) printf(\ else printf(\ for( i=1; i<=n; i++ ) g[i].clear(); } return 0; }

/*婚配问题*/ /*

设王子的集合为A，设公主的集合为B 1)从A到B建边

2)对于原题中给定的匹配建立反向边

3)求强连通分量，同一个连通分量的即是答案！*/

#include #include #include #include using namespace std; const int NN = 4005; int n,m,ans[NN]; vector g[NN];

46

int pre[NN],low[NN],sc[NN],s[NN],top,cnt0,cnt1; void SCdfs( int u ) { int i,v,min; min = pre[u] = low[u] = cnt0++; s[top++] = u; for( i=0; i

void solve() { int i,j,v,cnt; memset( pre,-1,sizeof(pre) ); top = cnt0 = cnt1 = 0; for( i=1; i<=n; i++ ) if( pre[i]==-1 ) SCdfs( i ); for( i=1; i<=n; i++ ){ for( cnt=j=0; j

int main() { int i,j; while( scanf(\ for( i=1; i<=n; i++ ){ scanf(\ while( m-- ){

47

scanf(\ g[i].push_back( j+n ); } } for( i=1; i<=n; i++ ){ scanf(\ g[j+n].push_back( i ); } solve(); for( i=1; i<=2*n; i++ ) g[i].clear(); } return 0; }

/*最小平均割边集

给出一个带权无向图GVE (V,E)，每条边e有一个权w 。求将点s和点t分开的一个边割 集C，使得该割集的平均边权最小. */ #include #include #include

const int NN = 105;

const double INF = 1e99; const double EPS = 1e-9;

int s,t,deg[NN],adj[NN][NN],que[NN],pre[NN]; int n,m,edge[4*NN][2],ans[4*NN]; bool use[4*NN];

double up,ret,cost[4*NN],cap[NN][NN],flow[NN][NN]; bool bfs() { int i,u,v,front,tail; memset( pre,-1,sizeof(pre) ); front = tail = 0; que[tail++] = s; pre[s] = s; while( frontEPS ){ pre[v] = u; if( v==t ) return true; que[tail++] = v; } }

48

} return false; }

void argument() { int u;double ex=INF; for( u=t; u!=s; u=pre[u] )if( cap[pre[u]][u]-flow[pre[u]][u]

double process( double p ) { int i,j,u,v; double w; ret = 0.0; memset( use,false,sizeof(use) ); memset( deg,0,sizeof(deg) ); for( i=1; i<=n; i++ ) for( j=1; j<=n; j++ ) flow[i][j] = 0.0; for( i=1; i<=m; i++ ){ w = cost[i]-p; if( w

void solve() { double l,r,mid,f; l = 0.0; r = up; while( 1 ){ mid = (l+r)/2; f = process( mid );

49

if( fabs(f)EPS ) l = mid+EPS; else r = mid-EPS; } int cnt=0,u,v,i; for( i=1; i<=m; i++ ){ u = edge[i][0]; v = edge[i][1]; if( use[i] ) ans[cnt++] = i; else if( pre[v]==-1&&pre[u]!=-1||pre[u]==-1&&pre[v]!=-1 ) ans[cnt++] = i; } printf(\ printf(\ for( i=1; i

int main() { int i; while( scanf(\ for( up=0.0,i=1; i<=m; i++ ){ scanf(\ up += cost[i]; } solve(); } return 0; }

二分图的相关性质

(1) 二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。

(2) 二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。

(3) DAG的最小路径覆盖(在原图的基础上面直接求就可以了) /*

pku2594有向无环图的最小路径覆盖，各个点集可以有交叉！ 1)求一个传递闭包

2)在传递闭包的基础上求一个最小路径覆盖 */

/* 最大匹配 */

注意：最小覆盖==最大匹配 #include #include

50

本文来源：https://www.bwwdw.com/article/w96o.html