[C++知识库]C++板子

GAUSS

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define exp 1e-8
#define RE register
#define IL inline
using namespace std;
double f[110],a[110][110];
bool flag[110],light[110];
struct formula
{
	double s[110];
}s[110];
IL int GAUSS(RE int n,formula* s,double* ans,bool* flag,bool* sign)
{
	RE int i,j,k,l;
	RE double tmp;
	RE bool res;
	memset(flag,0,sizeof(flag));
	memset(sign,0,sizeof(sign));
	for(i=l=1;i<=n&&l<=n;++i,++l)
	{
		for(j=i+1,k=i;j<=n;++j)if(fabs(s[k].s[l])<fabs(s[j].s[l]))k=j;
		if(i^k)swap(s[i],s[k]);
		if(fabs(s[i].s[l])<exp){flag[l]=1,--i;continue;}
		for(j=1;j<=n;++j)
			if(i^j&&fabs(s[j].s[l])>=exp)
				for(tmp=s[j].s[l]/s[i].s[l],s[j].s[0]-=s[i].s[0]*tmp,k=l;k<=n;++k)
					s[j].s[k]-=s[i].s[k]*tmp;
	}
	for(res=0,i=1;i<=n;sign[i]=bool(j>n),res|=sign[i],++i)
		if(fabs(s[i].s[0])>=exp)
			for(j=1;j<=n&&fabs(s[i].s[j])<exp;++j);
	if(res)return -1;
	for(res=0,i=1;i<=n;res|=flag[i],++i)if(!flag[i])ans[i]=s[i].s[0]/s[i].s[i];
	if(res)return 0;
	return 1;
}
int main()
{
	int n,i,j,ans;
	scanf("%d",&n);
	for(i=1;i<=n;scanf("%lf",&s[i].s[0]),++i)
		for(j=1;j<=n;++j)
			scanf("%lf",&s[i].s[j]);
	ans=GAUSS(n,s,f,flag,light);
/*	for(i=1;i<=n;printf("%.2lf\n",s[i].s[0]),++i)
		for(j=1;j<=n;++j)
			printf("%.2lf ",s[i].s[j]);*/
	if(ans==-1||ans==0)printf("No Solution");
	else
	for(i=1;i<=n;++i)printf("%.2lf\n",f[i]);
/*	if(ans==-1)
	{
		printf("\nNo solution\n");
		for(i=1;i<=n;++i)
			if(light[i])
				printf("%d\n",i);
	}
	if(ans==0)
	{
		printf("\nFree\n");
		for(i=1;i<=n;++i)
			if(flag[i])
				printf("%d\n",i);
	}
	if(ans==1)printf("\nSolution\n");*/
	return 0;
}

树剖

#include <cstdio>
#define IL inline
#define RE register
#define N 30010
#define E 60010
#define INF 2147483647
#define swap(x, y) x ^= y, y ^= x, x ^= y
using namespace std;
int head[N], e[E], nxt[E], tot;
int tree[N], mx[N << 2], sum[N << 2];
int dep[N], top[N], dfn[N], fa[N], siz[N], big[N], cnt;
int s[N], n;
IL int max(RE int x, RE int y) { return x > y ? x : y; }
IL void add(RE int x, RE int y) {
    e[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    e[++tot] = x, nxt[tot] = head[y], head[y] = tot;
    return;
}
IL void build(RE int x, RE int l, RE int r) {
    if (l == r) {
        mx[x] = sum[x] = tree[l];
        return;
    }
    RE int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    return;
}
IL void change(RE int x, RE int l, RE int r, RE int w, RE int v) {
    if (l == r) {
        mx[x] = sum[x] = v;
        return;
    }
    RE int mid = (l + r) >> 1;
    if (w <= mid)
        change(x << 1, l, mid, w, v);
    else
        change(x << 1 | 1, mid + 1, r, w, v);
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    return;
}
IL int query_max(RE int x, RE int l, RE int r, RE int left, RE int right) {
    if (left <= l && r <= right)
        return mx[x];
    RE int mid = (l + r) >> 1, ans = -INF;
    if (left <= mid)
        ans = max(ans, query_max(x << 1, l, mid, left, right));
    if (right > mid)
        ans = max(ans, query_max(x << 1 | 1, mid + 1, r, left, right));
    return ans;
}
IL int query_sum(RE int x, RE int l, RE int r, RE int left, RE int right) {
    if (left <= l && r <= right)
        return sum[x];
    RE int mid = (l + r) >> 1, ans = 0;
    if (left <= mid)
        ans += query_sum(x << 1, l, mid, left, right);
    if (right > mid)
        ans += query_sum(x << 1 | 1, mid + 1, r, left, right);
    return ans;
}
IL int querymax(RE int x, RE int y) {
    RE int ans;
    for (ans = -INF; top[x] != top[y]; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans = max(ans, query_max(1, 1, n, dfn[top[x]], dfn[x]));
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans = max(ans, query_max(1, 1, n, dfn[x], dfn[y]));
    return ans;
}
IL int querysum(RE int x, RE int y) {
    RE int ans;
    for (ans = 0; top[x] != top[y]; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans += query_sum(1, 1, n, dfn[top[x]], dfn[x]);
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans += query_sum(1, 1, n, dfn[x], dfn[y]);
    return ans;
}
IL void dfs(RE int x, RE int y) {
    dep[x] = dep[y] + 1, fa[x] = y, siz[x] = 1;
    for (RE int i = head[x]; i; i = nxt[i])
        if (e[i] != y) {
            dfs(e[i], x), siz[x] += siz[e[i]];
            if (siz[e[i]] > siz[big[x]])
                big[x] = e[i];
        }
    return;
}
IL void DFS(RE int x, RE int y) {
    dfn[x] = ++cnt, tree[cnt] = s[x], top[x] = y;
    if (big[x])
        DFS(big[x], y);
    for (int i = head[x]; i; i = nxt[i])
        if (e[i] != fa[x] && e[i] != big[x])
            DFS(e[i], e[i]);
    return;
}
int main() {
    //	freopen("data1.in","r",stdin);
    //	freopen("tree.out","w",stdout);
    char str[10];
    RE int i;
    int x, y, q;
    scanf("%d", &n), cnt = tot = 0;
    for (i = 1; i < n; ++i) scanf("%d%d", &x, &y), add(x, y);
    for (i = 1; i <= n; ++i) scanf("%d", &s[i]);
    fa[1] = 1, dfs(1, 0), DFS(1, 1), build(1, 1, n);
    for (scanf("%d", &q); q; --q) {
        scanf("%s%d%d", str, &x, &y);
        switch (str[1]) {
            case 'H':
                change(1, 1, n, dfn[x], y);
                break;
            case 'M':
                printf("%d\n", querymax(x, y));
                break;
            case 'S':
                printf("%d\n", querysum(x, y));
                break;
        }
    }
    //	fclose(stdin);
    //	fclose(stdout);
    return 0;
}

网络流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const long long N=210,E=10010;
long long head[N],to[E],nxt[E],val[E],dep[N],cur[N],t,n,tot=1;
bool vis[N];
void add(long long u,long long v,long long w)
{
	to[++tot]=v,val[tot]=w,nxt[tot]=head[u],head[u]=tot;
	return;
}
long long BFS(long long s)//分层图，删去无用边
{
	long long i,u;
	queue<long long>que;
	memset(dep,0,sizeof(dep));
	memset(vis,0,sizeof(vis));
	for(i=1; i<=n; i++)cur[i]=head[i];
	for(dep[s]=1,que.push(s); que.size(); que.pop())
		for(i=head[u=que.front()]; i; i=nxt[i])
			if(val[i]&&!dep[to[i]])
			{
				dep[to[i]]=dep[u]+1;
				if(!vis[to[i]])
					vis[to[i]]=1,que.push(to[i]);
			}
	return dep[t];
}
long long DFS(long long x,long long flow)
{
	long long ans=0,sum;
	if(x==t)return flow;
	for(long long &i=cur[x]; i&&ans<flow; i=nxt[i])//当前弧优化:在下一次DFS时不走原来head[x]那条边
		if(val[i]&&dep[x]+1==dep[to[i]]&&(sum=DFS(to[i],min(flow-ans,val[i]))))//上一行:剩余优化:没有剩余流量结束循环
			ans+=sum,val[i]-=sum,val[i^1]+=sum;//多路增广:没有直接返回,继续找增广路
	if(ans<flow)dep[x]=0;//删点优化:有流未增广完,当前点已用极致,下次无需访问该点
	return ans;
}
long long Dinic(long long s)
{
	long long ans;
	for(ans=0; BFS(s); ans+=DFS(s,0x7f7f7f7f));
	return ans;
}
int main()
{
	long long m,s,u,v,w,i;
	for(scanf("%lld%lld%lld%lld",&n,&m,&s,&t),i=1; i<=m; ++i)
		scanf("%lld%lld%lld",&u,&v,&w),add(u,v,w),add(v,u,0);
	printf("%lld\n",Dinic(s));
	return 0;
}

费用流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define RE register
#define IL inline
#define LL long long
#define INF 0x7f7f7f7f
#define mxe 65000
#define mxn 500
using namespace std;
LL e[(mxe << 1) + 10], v[(mxe << 1) + 10], w[(mxe << 1) + 10], nxt[(mxe << 1) + 10], head[mxn + 10],
    cur[mxn + 10], tot = 1, dis[mxn + 10], s, t;
bool vis[mxn + 10];
LL sum, ans;
IL void add(RE LL x, RE LL y, RE LL val, RE LL weight) {
    e[++tot] = y, v[tot] = val, w[tot] = weight, nxt[tot] = head[x], head[x] = tot;
    e[++tot] = x, v[tot] = 0, w[tot] = -weight, nxt[tot] = head[y], head[y] = tot;
    return;
}
IL bool SPFA(LL dl, LL dr) {
    RE LL i, u;
    queue<LL> que;
    for (i = dl; i <= dr; ++i) vis[i] = 0, dis[i] = INF, cur[i] = head[i];
    for (vis[s] = 1, dis[s] = 0, que.push(s); que.size();)
        for (i = head[u = que.front()], vis[u] = 0, que.pop(); i; i = nxt[i])
            if (v[i] && dis[e[i]] > dis[u] + w[i]) {
                dis[e[i]] = dis[u] + w[i];
                if (!vis[e[i]])
                    vis[e[i]] = 1, que.push(e[i]);
            }
    memset(vis, 0, sizeof(vis));
    return dis[t] != INF;
}
IL LL DFS(LL x, LL flow) {
    LL val, res = 0;
    if (x == t) {
        sum += flow, ans += flow * dis[t];
        return flow;
    }
    vis[x] = 1;
    for (LL &i = cur[x]; i; i = nxt[i])
        if (!vis[e[i]] && v[i] && dis[x] + w[i] == dis[e[i]])
            if ((val = DFS(e[i], min(v[i], flow - res)))) {
                v[i] -= val, v[i ^ 1] += val, res += val;
                if (res == flow)
                    break;
            }
    if (res == flow)
        vis[x] = 0;
    return res;
}
IL LL Dinic(LL dl, LL dr) {
    for (ans = sum = 0; SPFA(dl, dr); DFS(s, INF))
        ;
    return ans;
}
LL b[260];
int main() {
    LL n, m, i, j, a, c;
    scanf("%lld%lld", &m, &n);
    s = n + m + 1, t = s + 1;
    for (i = 1; i <= n; ++i) scanf("%lld", &a), add(s, i, a, 0);
    for (i = 1; i <= m; ++i)
        for (j = 1; j <= n; ++j) {
            scanf("%lld", &a);
            if (a)
                add(j, i + n, INF, 0);
        }
    for (i = 1; i <= m; ++i) {
        for (scanf("%lld", &c), j = 1; j <= c; ++j) scanf("%lld", b + j);
        for (b[0] = 0, b[c + 1] = INF, j = 0; j <= c; ++j)
            scanf("%lld", &a), add(i + n, t, b[j + 1] - b[j], a);
    }
    printf("%lld\n", Dinic(1, t));
    return 0;
}