下雪了

POJ2387 – Til the Cows Come Home(最短路/SPFA)

刚学了SPFA,利用队列来松弛边,虽然没DJ稳定,但是可以用来判断负环和负边权,记下来emmm

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int to;
    int w;
    unit() {};
    unit(int a, int b) :to(a), w(b) {};
};

vector<unit> G[1005];
int dis[1005];
bool v[1005];

void spfa(int s,int n)
{
    ffor(i, 1, n)
    {
        v[i] = false;
        dis[i] = IMAX;
    }
    dis[s] = 00;
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        v[f] = false;
        for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
        {
            unit u = *it;
            if (dis[f] + u.w < dis[u.to])
            {
                dis[u.to] = dis[f] + u.w;
                if (!v[u.to])
                {
                    q.push(u.to);
                    v[u.to] = true;
                }
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> m >> n;
    ffor(i, 1, m)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        G[x].push_back(unit(y, z));
        G[y].push_back(unit(x, z));
    }
    spfa(1, n);
    cout << dis[n] << endl;
}

 

CodeForces 1000D – Yet Another Problem On a Subsequence (DP/递推)

求题目所给的子串的总数emmm

从最后开始递推自己序列加后面数的子序列个数*间隔的组合数可以构成的子序列就是答案,所以从最后开始递推,递推出以每一位开头合理的子序列个数,然后累加起来就好了。

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

ll tab[1005];
ll dp[1005];
ll C[1005][1005];
void get_C(int maxn)
{
    C[0][0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 998244353;
    }
}

int main()
{
    get_C(1004);
    ll n;
    while (cin >> n)
    {
        mes(tab, 0);
        mes(dp, 0);
        ffor(i, 1, n)
            scanf("%lld", &tab[i]);
        dp[n + 1] = 1;
        rfor(i, n, 1)
        {
            if (tab[i] > 0)
            {
                ffor(k, tab[i], n)
                {
                    if (k + i <= n)
                        dp[i] = (dp[i] + dp[i + k + 1] * C[k][tab[i]]) % 998244353;
                }
            }
        }
        ll res = 0;
        ffor(i, 1, n)
            res = (res + dp[i]) % 998244353;
        cout << res << endl;
    }
}

 

POJ 3281 – Dining(最大流+花式建图)

为了满足各种要求来做成网络流也是煞费苦心啊!

引用一下CSDN的某张图,这道题巧妙地把牛拆成了两个点来同时满足两个条件。

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
	int num;
	int w;
	int rev;
	unit() {};
	unit(int n, int ww,int r) :num(n), w(ww),rev(r) {};
};
vector<unit> G[501];
int dep[501];
int cur[501];
int n, m, cnt, st, ed;

void add(int x, int y, int z)
{
	G[x].push_back(unit(y, z, G[y].size()));
	G[y].push_back(unit(x, 0, G[x].size() - 1));
}

bool bfs()
{
	mes(dep, 0);
	queue<int> q;
	q.push(st);
	dep[st] = 1;
	while (!q.empty())
	{
		int f = q.front();
		q.pop();
		for (vector<unit>::iterator it=G[f].begin();it!=G[f].end();it++)
		{
			unit u = *it;
			if (u.w && !dep[u.num])
			{
				dep[u.num] = dep[f] + 1;
				q.push(u.num);
				if (u.num == ed)return true;
			}
		}
	}
	return false;
}

int dfs(int x, int f)
{
	if (x == ed)
		return f;
	for (int& i = cur[x]; i <= G[x].size() - 1; i++)
	{
		unit& u = G[x][i];
		if (u.w && dep[u.num] == dep[x] + 1)
		{
			int flow = dfs(u.num, min(f, u.w));
			if (flow > 0)
			{
				u.w -= flow;
				G[u.num][u.rev].w += flow;
				return flow;
			}
		}
	}
	return 0;
}

int dinic()
{
	int res = 0;
	while (bfs())
	{
		mes(cur, 0);
		res += dfs(st, IMAX);
	}
	return res;
}

int main()
{
	int n, a, b;
	cin >> n >> a >> b;
	st = 0;
	ed = n * 2 + a + b + 1;
	ffor(i, n * 2 + 1, n * 2 + a)
		add(st, i, 1);
	ffor(i, n * 2 + a + 1, n * 2 + a + b)
		add(i, ed, 1);
	ffor(i, 1, n)
	{
		add(i, i + n, 1);
		int x, y;
		scanf("%d%d", &x, &y);
		ffor(v, 1, x)
		{
			int xx;
			scanf("%d", &xx);
			xx += n * 2;
			add(xx, i, 1);
		}
		ffor(v, 1, y)
		{
			int yy;
			scanf("%d", &yy);
			yy += n * 2 + a;
			add(i + n, yy, 1);
		}
	}
	printf("%d\n", dinic());
}