模板题，答案需要-1，三个村只需要两条路



```cpp
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1000;

int father[maxn];

int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void unionn(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        father[root_x] = root_y;
    }
}

int main() {
    int n, m;
    while (cin >> n >> m && n != 0) {
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
        }

        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            unionn(a, b);
        }

        // Count the number of unique sets
        int unique_sets = 0;
        for (int i = 1; i <= n; ++i) {
            if (father[i] == i) {
                unique_sets++;
            }
        }

        // Calculate the number of roads needed to connect all sets
        int roads_needed = unique_sets - 1;

        cout << roads_needed << endl;
    }

    return 0;
}

```

P1536

这里的坑不少

女生是负数，数组下标有负数，所以要先变成正数,但是直接并查集会出现男生女生重合，编号相同，所以要把女生映射到+n上，这样就完美



```cpp
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 500000;
int father[maxn];

int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void unionn(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        father[root_y] = root_x;
    }
}

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

    for (int i = 1; i <= n + m; ++i) {
        father[i] = i;
    }

    for (int i = 1; i <= p; ++i) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            unionn(a, b);
        }
    }

    for (int i = 1; i <= q; ++i) {
        int a, b;
        cin >> a >> b;
        a *= -1;
        b *= -1;
        if (find(a + n) != find(b + n)) {
            unionn(a + n, b + n);
        }
    }

    int ansm = 0, ansf = 0;

    for (int i = 1; i <= n; ++i) {
        if (find(i) == find(1)) {
            ansm++;
        }
    }

    for (int i = n + 1; i <= n + m; ++i) {
        if (find(i) == find(n + 1)) {
            ansf++;
        }
    }

    int result = min(ansm, ansf);
    cout << result << endl;

    return 0;
}

```

P2078


```go
func (cm *ConsensusModule) persistToStorage() {
	var termData bytes.Buffer
	if err := gob.NewEncoder(&termData).Encode(cm.currentTerm); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("currentTerm", termData.Bytes())

	var votedData bytes.Buffer
	if err := gob.NewEncoder(&votedData).Encode(cm.votedFor); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("votedFor", votedData.Bytes())

	var logData bytes.Buffer
	if err := gob.NewEncoder(&logData).Encode(cm.log); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("log", logData.Bytes())
}


// Submit submits a new command to the CM. This function doesn't block; clients
// read the commit channel passed in the constructor to be notified of new
// committed entries. It returns true iff this CM is the leader - in which case
// the command is accepted. If false is returned, the client will have to find
// a different CM to submit this command to.
func (cm *ConsensusModule) Submit(command interface{}) bool {
	cm.mu.Lock()
	cm.dlog("Submit received by %v: %v", cm.state, command)
	if cm.state == Leader {
		cm.log = append(cm.log, LogEntry{Command: command, Term: cm.currentTerm})
		cm.persistToStorage()
		cm.dlog("... log=%v", cm.log)
		cm.mu.Unlock()
		cm.triggerAEChan <- struct{}{}
		return true
	}

	cm.mu.Unlock()
	return false
}


// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	lastLogIndex, lastLogTerm := cm.lastLogIndexAndTerm()
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d, log index/term=(%d, %d)]", args, cm.currentTerm, cm.votedFor, lastLogIndex, lastLogTerm)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) &&
		(args.LastLogTerm > lastLogTerm ||
			(args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIndex)) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}

func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {

```



raft持久化

```go
func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("AppendEntries: %+v", args)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in AppendEntries")
		cm.becomeFollower(args.Term)
	}

	reply.Success = false
	if args.Term == cm.currentTerm {
		if cm.state != Follower {
			cm.becomeFollower(args.Term)
		}
		cm.electionResetEvent = time.Now()

		// Does our log contain an entry at PrevLogIndex whose term matches
		// PrevLogTerm? Note that in the extreme case of PrevLogIndex=-1 this is
		// vacuously true.
		if args.PrevLogIndex == -1 ||
			(args.PrevLogIndex < len(cm.log) && args.PrevLogTerm == cm.log[args.PrevLogIndex].Term) {
			reply.Success = true

			// Find an insertion point - where there's a term mismatch between
			// the existing log starting at PrevLogIndex+1 and the new entries sent
			// in the RPC.
			logInsertIndex := args.PrevLogIndex + 1
			newEntriesIndex := 0

			for {
				if logInsertIndex >= len(cm.log) || newEntriesIndex >= len(args.Entries) {
					break
				}
				if cm.log[logInsertIndex].Term != args.Entries[newEntriesIndex].Term {
					break
				}
				logInsertIndex++
				newEntriesIndex++
			}
			// At the end of this loop:
			// - logInsertIndex points at the end of the log, or an index where the
			//   term mismatches with an entry from the leader
			// - newEntriesIndex points at the end of Entries, or an index where the
			//   term mismatches with the corresponding log entry
			if newEntriesIndex < len(args.Entries) {
				cm.dlog("... inserting entries %v from index %d", args.Entries[newEntriesIndex:], logInsertIndex)
				cm.log = append(cm.log[:logInsertIndex], args.Entries[newEntriesIndex:]...)
				cm.dlog("... log is now: %v", cm.log)
			}

			// Set commit index.
			if args.LeaderCommit > cm.commitIndex {
				cm.commitIndex = intMin(args.LeaderCommit, len(cm.log)-1)
				cm.dlog("... setting commitIndex=%d", cm.commitIndex)
				cm.newCommitReadyChan <- struct{}{}
			}
		} else {
			// No match for PrevLogIndex/PrevLogTerm. Populate
			// ConflictIndex/ConflictTerm to help the leader bring us up to date
			// quickly.
			if args.PrevLogIndex >= len(cm.log) {
				reply.ConflictIndex = len(cm.log)
				reply.ConflictTerm = -1
			} else {
				// PrevLogIndex points within our log, but PrevLogTerm doesn't match
				// cm.log[PrevLogIndex].
				reply.ConflictTerm = cm.log[args.PrevLogIndex].Term

				var i int
				for i = args.PrevLogIndex - 1; i >= 0; i-- {
					if cm.log[i].Term != reply.ConflictTerm {
						break
					}
				}
				reply.ConflictIndex = i + 1
			}
		}
	}

	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("AppendEntries reply: %+v", *reply)
	return nil
}
```


```go
// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	lastLogIndex, lastLogTerm := cm.lastLogIndexAndTerm()
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d, log index/term=(%d, %d)]", args, cm.currentTerm, cm.votedFor, lastLogIndex, lastLogTerm)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) &&
		(args.LastLogTerm > lastLogTerm ||
			(args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIndex)) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}
```

raft两个重要的RPC

任务不会消耗时间，这是一个贪心题目，首先肯定会想到，完成任务并不会消耗时间，但你的时间得大于所需时间。



首先肯定是先完成b更大的因为能获得的时间更多之后能完成的任务也更多，但是所有都按b从大到小排序

做完b大于0的任务后，T=10，剩下2组任务：t1=9，b1=-5；t2=4，b2=-2；显然如果先做第二个的话，会使得第一个任务不能完成

我们可以这样想：对于两组任务t1、b1、t2、b2（其中b1、b2全为负）且当时的时间为T，若先做第一个任务会使得不能做第二个任务而先做第二个任务后还能继续完成第一个任务，则会有

T+b1<t2,T+b2>t1;

移项可得

T<t2-b1,T>t1-b2;

根据不等式的传递性可知

t1-b2<T<t2-b1即t1+b1<t2+b2;

所以我们可以看出按照b+t从大到小的顺序排序可使得答案最优
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Task {
    int t;
    int b;

    Task(int time, int bonus) : t(time), b(bonus) {}
};

bool comparePositive(const Task& a, const Task& b) {
    return a.t < b.t; // Sort positive bonus tasks by time
}

bool compareNegative(const Task& a, const Task& b) {
    return (a.t + a.b) > (b.t + b.b); // Sort negative bonus tasks by (time + bonus)
}

int main() {
    int Z;
    cin >> Z;

    while (Z--) {
        int n, T;
        cin >> n >> T;

        vector<Task> positive;
        vector<Task> negative;

        for (int i = 0; i < n; i++) {
            int t, b;
            cin >> t >> b;
            Task task(t, b);
            if (b > 0) {
                positive.push_back(task);
            } else {
                negative.push_back(task);
            }
        }

        sort(positive.begin(), positive.end(), comparePositive);
        sort(negative.begin(), negative.end(), compareNegative);

        bool success = true;

        for (const Task& task : positive) {
            if (T > task.t) {
                T += task.b;
            } else {
                success = false;
                break;
            }
        }

        for (const Task& task : negative) {
            if (T > task.t) {
                T += task.b;
            } else {
                success = false;
                break;
            }

            if (T <= 0) {
                success = false;
                break;
            }
        }

        if (success) {
            cout << "+1s" << endl;
        } else {
            cout << "-1s" << endl;
        }
    }

    return 0;
}

```