xanxusII

2119

2774577882
lalalal
٩ˊωˋو_7
RyanMoriarty

7889
zfs
shenhaomin
down
Sean今天AC了吗
MZZDX

IceCola丶
MYCF
shaoxuan

f[i]: 价值为I时，需要的最小体积

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e6 + 10;

int f[N];

int n, m;
int main(){

cin >> n >> m;
memset(f, 0x3f, sizeof f);
f[0] = 0;
int mx = 0;
for(int i = 0; i < n; i++){
int vi, wi;
cin >> vi >> wi;
mx = max(mx, (m + vi - 1)/ vi * wi);
for(int j = wi; j <= mx; j++){
f[j] = min(f[j], f[j - wi] + vi);
}

}

int res =  0;

for(int j = mx; j >= 0; j--){
if(f[j] <= m){res = j; break;}
}
cout << res << endl;

return 0;

}


f[i]: 体积为i时, 背包装的最大价值

#include<iostream>
using namespace std;

const int N = 1005;

int f[N][N], v[N], w[N];

int main(){
int n, m;
cin >> n >> m;

for(int i = 1; i <= n; i++){cin >> v[i] >> w[i];}

for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
f[i][j] = f[i - 1][j];
if(j >= v[i]){f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}
}
}

cout << f[n][m] << endl;
return 0;
}


f[i]: 价值为i时， 需要的最小体积

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e6 + 5;

int f[N];

int n, m;

int main(){
cin >> n >> m;

memset(f, 0x3f, sizeof f);
f[0] = 0;
int mx = 0;
for(int i = 0; i < n; i++){
int vi, wi;
cin >> vi >> wi;
mx += wi;
//for(int j = N - 1; j >= wi; j--)如果用N - 1作为最大值来循环,容易超时
for(int j = mx; j >= wi; j--){
f[j] = min(f[j], f[j - wi] + vi);
}
}

int res = 0;
for(int i = mx; i >= 0; i--){

if(f[i] <= m){res = i; break;}
}
cout << res << endl;
return 0;
}


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N], st[N];
int match[N];

bool find(int x)
{
for (int i = 1; i <= n; i ++ )
if (d[x][i] && !st[i])
{
st[i] = true;
int t = match[i];
if (t == 0 || find(t))
{
match[i] = x;
return true;
}
}

return false;
}

int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
d[a][b] = true;
}

// 传递闭包
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] |= d[i][k] & d[k][j];

int res = 0;
for (int i = 1; i <= n; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) res ++ ;
}

printf("%d\n", n - res);

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y)
{
for (int i = 0; i < 8; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
if (g[a][b]) continue;
if (st[a][b]) continue;

st[a][b] = true;

PII t = match[a][b];
if (t.x == 0 || find(t.x, t.y))
{
match[a][b] = {x, y};
return true;
}
}

return false;
}

int main()
{
cin >> n >> m >> k;

for (int i = 0; i < k; i ++ )
{
int x, y;
cin >> x >> y;
g[x][y] = true;
}

int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if (g[i][j] || (i + j) % 2) continue;
memset(st, 0, sizeof st);
if (find(i, j)) res ++ ;
}

cout << n * m - k - res << endl;

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, k;
int match[N];
bool g[N][N], st[N];

bool find(int x)
{
for (int i = 0; i < m; i ++ )
if (!st[i] && g[x][i])
{
st[i] = true;
if (match[i] == -1 || find(match[i]))
{
match[i] = x;
return true;
}
}

return false;
}

int main()
{
while (cin >> n, n)
{
cin >> m >> k;
memset(g, 0, sizeof g);
memset(match, -1, sizeof match);

while (k -- )
{
int t, a, b;
cin >> t >> a >> b;
if (!a || !b) continue;
g[a][b] = true;
}

int res = 0;
for (int i = 0; i < n; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) res ++ ;
}

cout << res << endl;
}

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool find(int x, int y)
{
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b])
{
st[a][b] = true;
PII t = match[a][b];
if (t.x == -1 || find(t.x, t.y))
{
match[a][b] = {x, y};
return true;
}
}
}

return false;
}

int main()
{
cin >> n >> m;

while (m -- )
{
int x, y;
cin >> x >> y;
g[x][y] = true;
}

memset(match, -1, sizeof match);

int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if ((i + j) % 2 && !g[i][j])
{
memset(st, 0, sizeof st);
if (find(i, j)) res ++ ;
}

cout << res << endl;

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;

if (u == root && h[u] == -1)
{
dcc_cnt ++ ;
dcc[dcc_cnt].push_back(u);
return;
}

int cnt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j])
{
cnt ++ ;
if (u != root || cnt > 1) cut[u] = true;
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
dcc[dcc_cnt].push_back(y);
} while (y != j);
dcc[dcc_cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[j]);
}
}

int main()
{
int T = 1;
while (cin >> m, m)
{
for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
idx = n = timestamp = top = dcc_cnt = 0;
memset(h, -1, sizeof h);
memset(dfn, 0, sizeof dfn);
memset(cut, 0, sizeof cut);

while (m -- )
{
int a, b;
cin >> a >> b;
n = max(n, a), n = max(n, b);
}

for (root = 1; root <= n; root ++ )
if (!dfn[root])
tarjan(root);

int res = 0;
ULL num = 1;
for (int i = 1; i <= dcc_cnt; i ++ )
{
int cnt = 0;
for (int j = 0; j < dcc[i].size(); j ++ )
if (cut[dcc[i][j]])
cnt ++ ;

if (cnt == 0)
{
if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
else res ++ ;
}
else if (cnt == 1) res ++, num *= dcc[i].size() - 1;
}

printf("Case %d: %d %llu\n", T ++, res, num);
}

return 0;
}



#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;

int cnt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (low[j] >= dfn[u]) cnt ++ ;
}
else low[u] = min(low[u], dfn[j]);
}

if (u != root) cnt ++ ;

ans = max(ans, cnt);
}

int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
memset(dfn, 0, sizeof dfn);
memset(h, -1, sizeof h);
idx = timestamp = 0;

while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
}

ans = 0;
int cnt = 0;
for (root = 0; root < n; root ++ )
if (!dfn[root])
{
cnt ++ ;
tarjan(root);
}

printf("%d\n", ans + cnt - 1);
}

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int from)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;

for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j])
is_bridge[i] = is_bridge[i ^ 1] = true;
}
else if (i != (from ^ 1))
low[u] = min(low[u], dfn[j]);
}

if (dfn[u] == low[u])
{
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
id[y] = dcc_cnt;
} while (y != u);
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
}

tarjan(1, -1);

for (int i = 0; i < idx; i ++ )
if (is_bridge[i])
d[id[e[i]]] ++ ;

int cnt = 0;
for (int i = 1; i <= dcc_cnt; i ++ )
if (d[i] == 1)
cnt ++ ;

printf("%d\n", (cnt + 1) / 2);

return 0;
}



#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 600010;

int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
int dist[N];

void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;

for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}

if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
sz[scc_cnt] ++ ;
} while (y != u);
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);

for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1);

while (m -- )
{
int t, a, b;
scanf("%d%d%d", &t, &a, &b);
if (t == 1) add(h, b, a, 0), add(h, a, b, 0);
else if (t == 2) add(h, a, b, 1);
else if (t == 3) add(h, b, a, 0);
else if (t == 4) add(h, b, a, 1);
else add(h, a, b, 0);
}

tarjan(0);

bool success = true;
for (int i = 0; i <= n; i ++ )
{
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a == b)
{
if (w[j] > 0)
{
success = false;
break;
}
}
else add(hs, a, b, w[j]);
}
if (!success) break;
}

if (!success) puts("-1");
else
{
for (int i = scc_cnt; i; i -- )
{
for (int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
dist[k] = max(dist[k], dist[i] + w[j]);
}
}

LL res = 0;
for (int i = 1; i <= scc_cnt; i ++ ) res += (LL)dist[i] * sz[i];

printf("%lld\n", res);
}

return 0;
}