抽空在vjudge上做了这套题。剩下FZU 2208数论题不会。
FZU 2205
这是个想法题，每次可以在上一次基础上加上边数/2的新边。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=; int f[N];
int main () {
f[]=;
for (int i=;i<=;i++) {
f[i]=f[i-]+i/;
}
int T;
cin>>T;
while (T--) {
int n;
cin>>n;
cout<<f[n]<<endl;
}
return ;
}
FZU 2206
乍看不知道什么东西，直接在机器上跑几个数字可以试出来结论。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=;
const int INF=0x3f3f3f3f; int main () {
//freopen("out.txt","r",stdin);
int T;
scanf("%d",&T);
for (int cas=;cas<=T;cas++) {
long long n;
scanf("%I64d",&n);
if (n<20150001LL) cout<<n+<<endl;
else cout<<<<endl;
}
return ;
}
FZU 2207
会用倍增算LCA的话，这题也肯定会做。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=; vector<int>e[N];
int fa[N][];
int dep[N];
void dfs(int u,int f,int d) {
dep[u]=d;
for (int i=;i<e[u].size();i++) {
int v=e[u][i];
if (v==f) continue;
dfs(v,u,d+);
fa[v][]=u;
}
} void calc(int n) {
for (int j=;j<=;j++) {
for (int i=;i<=n;i++) {
fa[i][j]=fa[fa[i][j-]][j-];
}
}
} int kthA(int u,int k) {
for (int i=;i>=;i--) {
if (k>=(<<i)){
k-=(<<i);
u=fa[u][i];
}
}
return u;
} int lca(int u,int v) {
if (dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
u=kthA(u,d);
if (u==v) return u;
for (int i=;i>=;i--) {
if (fa[u][i]==fa[v][i])
continue;
u=fa[u][i];
v=fa[v][i];
}
return fa[u][];
}
int main () {
int T;
scanf("%d",&T);
while (T--) {
int n,m;
scanf("%d %d",&n,&m);
for (int i=;i<=n;i++)
e[i].clear();
for (int i=;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(,-,);
calc(n);
static int cas=;
printf("Case #%d:\n",cas++);
while (m--) {
int u,v,k;
scanf("%d %d %d",&u,&v,&k);
int ans=lca(u,v);
if (k==) {
printf("%d\n",u);
continue;
}
else if (k==dep[u]-dep[ans]+dep[v]-dep[ans]+) {
printf("%d\n",v);
continue;
}
if (dep[u]-dep[ans]+>=k) {
int ret=kthA(u,k-);
printf("%d\n",ret);
}
else {
int to=dep[u]-dep[ans]+dep[v]-dep[ans]+-k;
int ret=kthA(v,to);
printf("%d\n",ret);
}
}
}
return ;
}
FZU 2208
数论题，不会
FZU 2209
分层图。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=;
const int INF=0x3f3f3f3f;
int get(int n,int u,int k) {
return k*n+u;
}
struct Edge {
int to,next,len;
Edge() {}
Edge(int _to,int _next,int _len):to(_to),next(_next),len(_len) {}
} edge[];
int idx=,head[N];
inline void addedge(int u,int v,int l) {
edge[++idx]=Edge(v,head[u],l);
head[u]=idx;
}
int dis[N][N],in[N];
bool vis[N];
bool spfa(int s,int n,int *dis) {
fill(dis,dis+N,INF);
memset(vis,false,sizeof(vis));
memset(in,,sizeof(in));
dis[s]=;
vis[s]=true;
queue<int> que;
que.push(s);
in[s]=;
while (!que.empty()) {
int u=que.front();
que.pop();
vis[u]=false;
for (int k=head[u];k;k=edge[k].next) {
int v=edge[k].to;
if (dis[v]>dis[u]+edge[k].len) {
dis[v]=dis[u]+edge[k].len;
if (!vis[v]) {
vis[v]=true;
in[v]++;
if (in[v]>n) return false;
que.push(v);
}
}
}
}
return true;
}
int main () {
//freopen("out.txt","r",stdin);
int T;
scanf("%d",&T);
for (int cas=;cas<=T;cas++) {
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
idx=;memset(head,,sizeof head);
for (int i=;i<=m;i++) {
int u,v;
scanf("%d %d",&u,&v);
int d;
for (int i=;i<;i++) {
scanf("%d",&d);
int uu=get(n,u,i);
int vv=get(n,v,(i+d)%);
addedge(uu,vv,d);
uu=get(n,v,i);
vv=get(n,u,(i+d)%);
addedge(uu,vv,d);
}
}
for (int i=;i<;i++) {
spfa(get(n,,i),n*,dis[i]);
}
printf("Case #%d:",cas);
while (k--) {
int v,s;
scanf("%d %d",&v,&s);
//cout<<"from "<<get(n,1,s)<<endl;
int ret=0x3f3f3f3f;
for (int i=;i<;i++) {
int p=get(n,v,i);
ret=min(ret,dis[s][p]);
}
if (ret==0x3f3f3f3f) ret=-;
printf(" %d",ret);
}
puts("");
}
return ;
}
FZU 2210
建立一个虚拟节点，连向所有粮仓，枚举所有禁止的城市，从虚拟节点dfs，更新答案。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=; vector<int>e[N];
int in[N];
bool vis[N];
int fob;
int cnt;
void dfs(int u) {
if (u==fob||vis[u]) return;
vis[u]=true;cnt++;
for (int i=;i<e[u].size();i++) {
int v=e[u][i];
dfs(v);
}
}
int main () {
int n,m;
while (scanf("%d %d",&n,&m)!=EOF) {
for (int i=;i<=n;i++){
e[i].clear();
in[i]=;
}
for (int i=;i<=m;i++) {
int u,v;
scanf("%d %d",&u,&v);
e[u].push_back(v);
in[v]++;
}
for (int i=;i<=n;i++) {
if (in[i]==)
e[].push_back(i);
}
int ret=n+,val=;
for (int i=n;i>=;i--) {
fob=i;
memset(vis,false,sizeof vis);
cnt=;
dfs();
cnt--;
if (n-cnt>=val) {
val=n-cnt;
ret=i;
}
}
cout<<ret<<endl;
}
return ;
}
FZU 2211
费用流，把所有蘑菇拆成两个点，根据时间关系，互相连边。农田的限制在于源点出来的流的大小。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
using namespace std; const int N=;
const int INF=0x3f3f3f3f; struct Edge{
int to,next,f;
long long c;
Edge(){}
Edge(int _to,int _nxt,int _f,long long _c):to(_to),next(_nxt),f(_f),c(_c){}
}edge[N<<]; int head[N],idx;
bool vis[N];
long long dis[N];
int pree[N],prev[N];
void addedge(int u,int v,int flow,long long cost){
edge[++idx]=Edge(v,head[u],flow,cost);
head[u]=idx;
edge[++idx]=Edge(u,head[v],,-cost);
head[v]=idx;
}
bool spfa(int s,int e){
memset(vis,,sizeof(vis));
memset(pree,-,sizeof(pree));
memset(prev,-,sizeof(prev));
for (int i=;i<N;i++) dis[i]=~0ULL>>;
dis[s]=;
vis[s]=true;
queue<int>que;
que.push(s);
while (!que.empty()){
int cur=que.front();
que.pop();
vis[cur]=false;
for (int k=head[cur];k;k=edge[k].next){
if (edge[k].f){
int n=edge[k].to;
if (dis[n]>dis[cur]+edge[k].c){
dis[n]=dis[cur]+edge[k].c;
prev[n]=cur;
pree[n]=k;
if (!vis[n]){
vis[n]=true;
que.push(n);
}
}
}
}
}
if (dis[e]>=INF) return ;
return ;
}
long long minCostMaxFlow(int src,int sink){
long long cur,min_val;
long long ansf=,ansc=;
while (spfa(src,sink)){
cur=sink;
min_val=INF;
while (prev[cur]!=-){
if (min_val>edge[pree[cur]].f)
min_val=edge[pree[cur]].f;
cur=prev[cur];
}
cur=sink;
while (prev[cur]!=-){
edge[pree[cur]].f-=min_val;
edge[pree[cur]^].f+=min_val;
cur=prev[cur];
}
ansc+=dis[sink]*min_val;
ansf+=min_val;
}
return ansc;
} int s[N],t[N],v[N];
int main () {
int T;
scanf("%d",&T);
for (int cas=;cas<=T;cas++) {
int n,m;
scanf("%d %d",&n,&m);
for (int i=;i<=m;i++) {
scanf("%d %d %d",s+i,t+i,v+i);
}
idx=;memset(head,,sizeof head);
for (int i=;i<=m;i++) {
for (int j=;j<=m;j++) {
if (t[i]<s[j]) {
addedge(i+m,j,INF,);
}
}
}
int s=m+m+,t=m+m++;
for (int i=;i<=m;i++) {
addedge(,i,INF,);
addedge(i,i+m,,-v[i]);
addedge(i+m,t,INF,);
}
addedge(s,,n,);
long long ret=-minCostMaxFlow(s,t);
cout<<ret<<endl;
}
return ;
}