HDU 3861 The King’s Problem
缩点后得到新图，在新图上跑最小路径覆盖，得到答案
The King’s Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4653 Accepted Submission(s): 1567
Problem Description
In the Kingdom of Silence, the king has a new problem. There are N cities in the kingdom and there are M directional roads between the cities. That means that if there is a road from u to v, you can only go from city u to city v, but can’t go from city v to city u. In order to rule his kingdom more effectively, the king want to divide his kingdom into several states, and each city must belong to exactly one state. What’s more, for each pair of city (u, v), if there is one way to go from u to v and go from v to u, (u, v) have to belong to a same state. And the king must insure that in each state we can ether go from u to v or go from v to u between every pair of cities (u, v) without passing any city which belongs to other state.
Now the king asks for your help, he wants to know the least number of states he have to divide the kingdom into.
Input
The first line contains a single integer T, the number of test cases. And then followed T cases.
The first line for each case contains two integers n, m(0 < n <= 5000,0 <= m <= 100000), the number of cities and roads in the kingdom. The next m lines each contains two integers u and v (1 <= u, v <= n), indicating that there is a road going from city u to city v.
Output
The output should contain T lines. For each test case you should just output an integer which is the least number of states the king have to divide into.
Sample Input
1
3 2
1 2
1 3
Sample Output
2
#include "bits/stdc++.h"
using namespace std;
const int maxn = 5010;
int low[maxn], dfn[maxn], ins[maxn], belong[maxn], Stack[maxn];
int in[maxn], out[maxn], link[maxn];
bool vis[maxn];
int n, m, INDEX, cnt, top;
vector<int> g1[maxn], g2[maxn];
void init() {
for(int i=0; i<maxn; ++i) g1[i].clear(), g2[i].clear();
memset(dfn,0,sizeof(dfn));
memset(ins,0,sizeof(ins));
memset(link,0,sizeof(link));
//memset(in,0,sizeof(in));
//memset(out,0,sizeof(out));
INDEX=cnt=top=0;
}
void tarjan(int u) {
int v;
dfn[u]=low[u]=++INDEX;
ins[u]=1;
Stack[++top]=u;
for(int i=0; i<g1[u].size(); ++i) {
v=g1[u][i];
if(!dfn[v]) {
tarjan(v);
if(low[v]<low[u]) low[u]=low[v];
}
else if(ins[v]&&dfn[v]<low[u]) low[u]=dfn[v];
}
if(dfn[u]==low[u]) {
cnt++;
while(1) {
v=Stack[top--];
ins[v]=0;
belong[v]=cnt;
if(v==u) break;
}
}
}
bool find(int x) {
//cout<<"hhh"<<endl;
for(int i=0; i<g2[x].size(); ++i) {
int v=g2[x][i];
if(!vis[v]) {
vis[v]=1;
if(link[v]==0||find(link[v])) {
link[v]=x;
return 1;
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
init();
cin>>n>>m;
for(int i=0; i<m; ++i) {
int a, b;
cin>>a>>b;
g1[a].push_back(b);
}
for(int i=1; i<=n; ++i) {
if(!dfn[i]) tarjan(i);
}
for(int i=1; i<=n; ++i) {
for(int j=0; j<g1[i].size(); ++j) {
int v=g1[i][j];
if(belong[i]!=belong[v]) g2[belong[i]].push_back(belong[v]); //得到新图
}
}
int ans=0;
for(int i=1; i<=cnt; ++i) {
memset(vis,0,sizeof(vis));
ans+=find(i);
} //最大匹配
cout<<cnt-ans<<endl; //最下路径覆盖
}
}
HDU 1269 迷宫城堡
这题直接缩点，如果缩成了一个点，则Yes，否则No。
迷宫城堡
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25366 Accepted Submission(s): 10863
Problem Description
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
Input
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
Output
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
Sample Output
Yes
No
Author
Gardon
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e4+10;
int N, M;
vector<int> lj[maxn];
int dfn[maxn], low[maxn], ins[maxn], INDEX, cnt;
stack<int> s;
void tarjan(int now) {
low[now]=dfn[now]=++INDEX;
s.push(now);
ins[now]=1;
for(int i=0; i<lj[now].size(); ++i) {
int v=lj[now][i];
if(dfn[v]==-1) {
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(ins[v]) {
low[now]=min(low[now],dfn[v]);
}
}
if(low[now]==dfn[now]) {
cnt++;
while(1) {
int v=s.top();
s.pop();
ins[v]=0;
if(now==v) break;
}
}
}
int main() {
ios::sync_with_stdio(false);
while(cin>>N>>M, N||M) {
for(int i=0; i<maxn; ++i) lj[i].clear();
memset(dfn,-1,sizeof(dfn));
memset(low,-1,sizeof(low));
memset(ins,0,sizeof(ins));
cnt=0;
for(int i=0; i<M; ++i) {
int s, t;
cin>>s>>t;
lj[s].push_back(t);
}
for(int i=1; i<=N; ++i) {
if(dfn[i]==-1) tarjan(i);
}
if(cnt==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
HDU 1827 Summer Holiday
仍然直接缩点，缩点后统计每个点的入度以及最小花费，最后若入度为零，则加上它的花费
Summer Holiday
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5223 Accepted Submission(s): 2290
Problem Description
To see a World in a Grain of Sand
And a Heaven in a Wild Flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
—— William Blake
听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？
Input
多组测试数组，以EOF结束。
第一行两个整数N和M（1<=N<=1000, 1<=M<=2000），表示人数和联系对数。
接下一行有N个整数，表示Wiskey联系第i个人的电话费用。
接着有M行，每行有两个整数X，Y，表示X能联系到Y，但是不表示Y也能联系X。
Output
输出最小联系人数和最小花费。
每个CASE输出答案一行。
Sample Input
12 16
2 2 2 2 2 2 2 2 2 2 2 2
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10
Sample Output
3 6
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e3+10;
int N, M;
vector<int> lj[maxn];
int dfn[maxn], low[maxn], ins[maxn], belong[maxn];
int mm[maxn], cost[maxn], in[maxn], cnt, INDEX;
stack<int> s;
void tarjan(int now) {
low[now]=dfn[now]=++INDEX;
s.push(now);
ins[now]=1;
for(int i=0; i<lj[now].size(); ++i) {
int v=lj[now][i];
if(!dfn[v]) {
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(ins[v]) {
low[now]=min(low[now],dfn[v]);
}
}
if(low[now]==dfn[now]) {
cnt++;
while(1) {
int v=s.top();
s.pop();
ins[v]=0;
belong[v]=cnt; //缩点后新的编号
if(now==v) break;
}
}
}
int main() {
ios::sync_with_stdio(false);
while(cin>>N>>M) {
for(int i=1; i<=N; ++i) cin>>cost[i];
for(int i=0; i<maxn; ++i) lj[i].clear();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(ins,0,sizeof(ins));
memset(in,0,sizeof(in));
memset(belong,0,sizeof(belong));
for(int i=1; i<=N; ++i) mm[i]=1e8;
while(s.size()) s.pop();
cnt=dp=0;
for(int i=0; i<M; ++i) {
int s, t;
cin>>s>>t;
lj[s].push_back(t);
}
for(int i=1; i<=N; ++i) if(!dfn[i]) tarjan(i);
for(int i=1; i<=N; ++i) {
for(int j=0; j<lj[i].size(); ++j) {
int v=lj[i][j];
if(belong[v]!=belong[i]) in[belong[v]]++; //统计入度
}
}
for(int i=1; i<=N; ++i) mm[belong[i]]=min(mm[belong[i]],cost[i]); //每个点的最小花费
int num=0, tot=0;
for(int i=1; i<=cnt; ++i) {
if(in[i]==0) num++, tot+=mm[i]; //入度为零，则加上花费
}
cout<<num<<' '<<tot<<endl;
}
}
HDU 2242 考研路茫茫——空***室(割边+树形dp)
我觉得我这代码是全网最短的啦。
（重边卡了我一小时0……0）
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e4 + 10;
int N, M;
vector<int> g[maxn];
vector<int> bridge; //记录割边（桥）
int dfn[maxn], low[maxn], ins[maxn], Stack[maxn], fat[maxn];
int top, INDEX;
int sum, dp[maxn];
map<int,int> cnt;
void init() {
for(int i=0; i<maxn; ++i) g[i].clear();
bridge.clear();
cnt.clear();
memset(dfn,-1,sizeof(dfn));
memset(low,-1,sizeof(low));
memset(ins,0,sizeof(ins));
memset(fat,-1,sizeof(fat));
sum=top=INDEX=0;
}
int tarjan(int u) { // 不用缩点，只需要找到割边，同时将所有dp值算出来（我真是个天才，2333）
int v;
dfn[u]=low[u]=INDEX++;
ins[u]=1;
Stack[++top]=u;
for(int i=0; i<g[u].size(); ++i) {
v=g[u][i];
fat[v]=u;
if(dfn[v]==-1) {
dp[u]+=tarjan(v);
if(low[v]<low[u]) low[u]=low[v];
else if(low[v]>dfn[u]&&cnt[u*1e5+v]==1) bridge.push_back(v); //要成为割边，则这条边不能是重边，因为题意说只能断开一条通道，巨坑！
}
else if(ins[v]&&fat[u]!=v&&dfn[v]<low[u]) low[u]=dfn[v]; //更新low[u]时，v不能是父节点
}
if(dfn[u]==low[u]) {
while(1) {
v=Stack[top--];
ins[v]=0;
if(v==u) break;
}
}
return dp[u];
}
int main() {
ios::sync_with_stdio(false);
while(cin>>N>>M) {
init();
for(int i=0; i<N; ++i) {
cin>>dp[i];
sum+=dp[i];
}
for(int i=0; i<M; ++i) {
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
cnt[u*1e5+v]++; // 简单哈希一下，记录同一条边的数量
cnt[v*1e5+u]++;
}
tarjan(0); // 由于是连通图，所有随便找个根节点dfs就行了。
if(bridge.size()==0) { //如果找不到割边，则你懂的。
cout<<"impossible"<<endl;
continue;
}
int mm=1e9;
for(int i=0; i<bridge.size(); ++i) {
if(mm>abs(sum-2*dp[bridge[i]])) mm=abs(sum-2*dp[bridge[i]]); //找到最小的差值
}
cout<<mm<<endl;
}
}
京公网安备 11010502036488号